#include<vector>
#include <string>
#include<algorithm>
#include <iostream>
#include <queue>
#include<set>
#include<cmath>
#include<math.h>
using namespace std;
#define ll long long
#define pll pair<long long, long long>
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define cin(a) for(ll ghgh = 0; ghgh<a.size(); ghgh++) cin»a[ghgh];
#define pcin(a) for(ll ghgh = 0; ghgh<a.size(); ghgh++) cin»a[ghgh].first»a[ghgh].second;
#define cout(a) for(ll ghgha = 0; ghgha<a.size(); ghgha++) cout<<a[ghgha]<<" ";
#define pcout(a) for(ll ghgha = 0; ghgha<a.size(); ghgha++) cout«a[ghgha].first«" "«a[ghgha].second«endl;
const ll inf = 1e18+123, llinf = 1e18 + 123;
void xru() {
    setlocale(LC_ALL, "rus");
    /*freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void dfsa(vector<vector<pll>>& g, vector<ll>& dist) {
    dist[0] = 0;
    vector<bool>used(g.size(), false);
    queue<ll>q;
    q.push(0);
    used[0] = true;
    while (!q.empty()) {
        ll x = q.front();
        q.pop();
        for (ll i = 0; i < g[x].size(); i++) {
            if (!used[g[x][i].first]) {
                dist[g[x][i].first] = dist[x] + 1;
                used[g[x][i].first] = true;
                q.push(g[x][i].first);
            }
        }
    }
}

void dfsb(vector<vector<pll>>& g, vector<ll>& dist) {
    dist[g.size()-1] = 0;
    vector<bool>used(g.size(), false);
    queue<ll>q;
    q.push(g.size()-1);
    used[g.size()-1] = true;
    while (!q.empty()) {
        ll x = q.front();
        q.pop();
        for (ll i = 0; i < g[x].size(); i++) {
            if (!used[g[x][i].first]) {
                dist[g[x][i].first] = dist[x] + 1;
                used[g[x][i].first] = true;
                q.push(g[x][i].first);
            }
        }
    }
}



void bfs(vector<vector<pll>>& g, vector<ll>& mindist) {
    ll n = g.size();
    vector<ll>dist(n, inf);
    vector<bool>flag(n, false), used(n, false);
    queue<ll>q;
    q.push(0);
    used[0] = true;
    dist[0] = 0;
    while (!q.empty()) {
        ll x = q.front();
        q.pop();
        //cout << x;
        if (!flag[x]) {
            for (ll i = 0; i < g[x].size(); i++) {
                pll to = g[x][i];
                if (!used[to.first] || dist[to.first] == dist[x]+1) {
                    mindist[dist[x] + 1] = min(mindist[dist[x] + 1], to.second);
                }

            }
            flag[x] = true;
            q.push(x);
        }
        else {
            for (ll i = 0; i < g[x].size(); i++) {
                pll to = g[x][i];
                if (!used[to.first]) {
                    dist[to.first] = dist[x] + 1;
                    used[to.first] = true;
                    if (to.second == mindist[dist[to.first]]) {
                        q.push(to.first);
                    }
                }
            }
        }
    }
}

bool comp(vector<ll>& a, vector<ll>& b) {
    if (a.size() != b.size()) {
        return false;
    }
    for (ll i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) {
            return false;
        }
    }
    return true;
}

void A(vector<vector<pll>>& g, ll& sz, vector<ll>&ans) {

    ll n = g.size();
    queue<pll>q;
    vector<ll>dist(n, inf);
    vector<bool>used(n, false);
    dist[n - 1] = 0;
    vector<pll>prev(n, {-1, -1});
    prev[n - 1] = { -1, -1 };
    q.push({ n - 1, 0 });
    while (!q.empty()) {
        pll x = q.front();
        q.pop();
        for (ll i = 0; i < g[x.first].size(); i++) {
            pll to = g[x.first][i];
            if (dist[x.first] + 1 < dist[to.first]) {
                prev[to.first].first = x.first;
                prev[to.first].second = to.second;
                dist[to.first] = dist[x.first] + 1;
            }
            else if (dist[x.first] + 1 == dist[to.first]) {
                if (to.second < prev[to.first].second) {
                    prev[to.first].first = x.first;
                    prev[to.first].second = to.second;
                }
            }
            if (!used[to.first]) {
                used[to.first] = true;
                q.push(to);
            }
        }


    }
    ll x = 0;
    while (prev[x].first != -1) {
        ans.push_back(prev[x].second);
        x = prev[x].first;

    }
}

int main()
{
    xru();
    while(true){

    ll n = (ll)rand()%10+2, m = (ll)rand()%10;
    //cin >> n >> m;
    vector<vector<ll>>check(n, vector<ll>(n, llinf));
    vector<ll>x(m), y(m), cnt(m);
    for (ll i = 0; i < m; i++) {
       // cin >> x[i] >> y[i] >> cnt[i];
        x[i] = 1 + (ll)rand() % n, y[i] = 1 + (ll)rand() % n,  cnt[i] = (ll)rand() % 10;
        x[i]--, y[i]--;
        if (x[i] == y[i]) continue;
        check[x[i]][y[i]] = min(check[x[i]][y[i]], cnt[i]);
        check[y[i]][x[i]] = check[x[i]][y[i]];
    }
    vector < vector<pll>>g(n), lg(n);
    for (ll i = 0; i < m; i++) {
        if (x[i] == y[i] || check[x[i]][y[i]] == llinf) continue;
        g[x[i]].push_back({ y[i], check[x[i]][y[i]] });
        g[y[i]].push_back({ x[i], check[x[i]][y[i]] });
        check[x[i]][y[i]] = llinf;
        check[y[i]][x[i]] = llinf;

    }

    vector<ll>ans2;
    ll sz = 0;
    A(g, sz, ans2);


    vector<ll> dista(n, inf), distb(n, inf);
    dfsa(g, dista);
    dfsb(g, distb);


    vector<ll>dist(n, inf);
    vector<bool>used(n, false);
    queue<ll>q;
    dist[0] = 0;
    used[0] = true;
    q.push(0);
    while (!q.empty()) {
        ll x = q.front();
        q.pop();
        for (ll i = 0; i < g[x].size(); i++) {
            pll to = g[x][i];
            if (!used[to.first]) {
                dist[to.first] = dist[x] + 1;
                used[to.first] = true;
                q.push(to.first);
                if (dista[to.first] + distb[to.first] == distb[0]) {
                    //cout <<11<<" "<< x <<" "<< to.first << endl;
                    lg[x].push_back(to);
                    lg[to.first].push_back({ x, to.second });
                }
            }
            else {
                if (dist[x] + 1 == dist[to.first]) {
                    if (dista[to.first] + distb[to.first] == distb[0]) {
                        // cout <<22<<" "<< x << " " << to.first << endl;
                        lg[x].push_back(to);
                        lg[to.first].push_back({ x, to.second });
                    }
                }
            }
        }
    }
    /*
    for (ll i = 0; i < n; i++) {
        cout << i + 1 << "  ";
        for (ll j = 0; j < lg[i].size(); j++) {
            cout << lg[i][j].first + 1 << "," << lg[i][j].second << " ";
        }
        cout << endl;
    }

    */
    vector<ll>ans;
    if (dist[n - 1] != inf) {


        vector<ll>mindist(dist[n - 1] + 1, inf);
        bfs(lg, mindist);
       // cout << dist[n - 1] << endl;
        for (ll i = 1; i < mindist.size(); i++) {
            ans.push_back(mindist[i]);
        }
    }
    if (!comp(ans, ans2)) {
        cout << n << " " << m << endl;
        for (ll i = 0; i < m; i++) {
            cout << x[i]+1 << " " << y[i]+1 << " " << cnt[i] << endl;
        }
        cout << endl;
        cout(ans);
        cout << endl;
        cout(ans2);
        break;
    }
    }
}