Run for beer

People in BubbleLand like to drink beer. Little do you know, beer here is so good and strong that every time you drink it your speed goes 10 times slower than before you drank it.

Birko lives in city Beergrade, but wants to go to city Beerburg. You are given a road map of BubbleLand and you need to find the fastest way for him. When he starts his journey in Beergrade his speed is 1. When he comes to a new city he always tries a glass of local beer, which divides his speed by 10.

The question here is what the minimal time for him to reach Beerburg is. If there are several paths with the same minimal time, pick the one that has least roads on it. If there is still more than one path, pick any.

It is guaranteed that there will be at least one path from Beergrade to Beerburg.

Input

The first line of input contains integer N — the number of cities in Bubbleland and integer M — the number of roads in this country. Cities are enumerated from 0 to N - 1, with city 0 being Beergrade, and city N - 1 being Beerburg. Each of the following M lines contains three integers a, b ( a ≠ b) and len. These numbers indicate that there is a bidirectional road between cities a and b with length len.

• 2 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 10⁵
• 0 ≤ len ≤ 9
• There is at most one road between two cities

Output

The first line of output should contain minimal time needed to go from Beergrade to Beerburg.

The second line of the output should contain the number of cities on the path from Beergrade to Beerburg that takes minimal time.

The third line of output should contain the numbers of cities on this path in the order they are visited, separated by spaces.

Examples

input

8 10
0 1 1
1 2 5
2 7 6
0 3 2
3 7 3
0 4 0
4 5 0
5 7 2
0 6 0
6 7 7

output

32
3
0 3 7

Solution:

#include <bits/stdc++.h>

using namespace std;

const int N = 400010;

vector < pair <int, int> > g[N];

int dist[N], x[N];
bool was[N];
int pr[N];

int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
    g[i].clear();
  }
  for (int i = 0; i < m; i++) {
    int foo, bar, qwe;
    scanf("%d %d %d", &foo, &bar, &qwe);
    g[foo].push_back(make_pair(bar, qwe));
    g[bar].push_back(make_pair(foo, qwe));
  }
  for (int i = 0; i < n; i++) {
    dist[i] = -1;
  }
  int b = 0, e = 0;
  x[0] = 0;
  dist[0] = 0;
  while (b <= e) {
    int sz = g[x[b]].size();
    for (int j = 0; j < sz; j++) {
      int u = g[x[b]][j].first;
      if (dist[u] == -1) {
        e++;
        x[e] = u;
        dist[u] = dist[x[b]] + 1;
      }
    }
    b++;
  }
  for (int i = 0; i < n; i++) {
    was[i] = false;
  }
  vector <int> can_be;
can_be.push_back(n - 1);
b = 0, e = 0;
was[n - 1] = true;
while (b <= e) {
    int v = can_be[b];
    int sz = g[v].size();
    for (int j = 0; j < sz; j++) {
      int u = g[v][j].first;
      if (!was[u] && g[v][j].second == 0) {
        e++;
        can_be.push_back(u);
        pr[u] = v;
        was[u] = true;
      }
    }
    b++;
  }
  int ddd = dist[n - 1];
  for (int i = 1; i < n; i++) {
    if (was[i]) {
      ddd = min(ddd, dist[i]);
    }
  }
  bool zeros = true;
  for (int pos = ddd; pos > 0; pos--) {
int ccnt = can_be.size();
int best = 42;
for (int id = 0; id < ccnt; id++) {
      int v = can_be[id];
      int sz = g[v].size();
      for (int j = 0; j < sz; j++) {
        int u = g[v][j].first;
        int cost = g[v][j].second;
        if (dist[u] + 1 == pos && cost < best) {
          best = cost;
        }
      }
    }
    if (best > 0) {
zeros = false;
}
if (pos == 1 || !zeros) {
printf("%d", best);
}
vector <int> new_can_be;
for (int id = 0; id < ccnt; id++) {
      int v = can_be[id];
      int sz = g[v].size();
      for (int j = 0; j < sz; j++) {
        int u = g[v][j].first;
        int cost = g[v][j].second;
        if (dist[u] + 1 == pos && cost == best && !was[u]) {
          was[u] = true;
          new_can_be.push_back(u);
          pr[u] = v;
        }
      }
    }
    can_be = new_can_be;
  }
  printf("\n");
  vector <int> ret;
int cur = 0;
ret.push_back(cur);
while (cur != n - 1) {
cur = pr[cur];
ret.push_back(cur);
}
printf("%d\n", ret.size());
for (int i = 0; i < (int)ret.size(); i++) {
    if (i > 0) putchar(' ');
printf("%d", ret[i]);
}
printf("\n");
return 0;
}