#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), pushed(n, false);
    queue<ll>q;
    q.push(0);
    used[0] = true;
    dist[0] = 0;
    pushed[0] = true;
    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);
                        pushed[to.first] = true;
                    }
                }
                else {
                    if (dist[to.first] == dist[x] + 1 && !pushed[to.first]) {
                        if (to.second == mindist[dist[to.first]]) {
                            q.push(to.first);
                            pushed[to.first] = true;
                        }
                    }
                }
            }
        }
    }
}

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;
        }
        if (a[i] < b[i]) {
            return true;
        }
    }
    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() % 13 + 2, m =1 + (ll)rand() % 7;
        //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() % 8;
            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;
        }
    }
}