#include <bits/stdc++.h>
#define F first
#define S second
const int NMAX = 5e4 + 5;
using namespace std;
priority_queue <pair < int ,int > > Q;
int n, m ,i , x , y , cost , f[NMAX] , nod , ok;
vector <pair <int,int> > a[NMAX];
pair <int,int > p;
int main()
{
    //ifstream fin("dijkstra.in");
    //ofstream fout("dijkstra.out");
   cin >> n >> m;
    for(i=1;i<=m;i++)
    {
        cin >> x >> y >> cost;
        a[x].push_back({y,cost});
    }
    Q.push({0  , 1});
    while(!Q.empty() and ok < 2)
    {
        p = Q.top();
        nod = p.S;
        cost = p.F;
        if(f[nod] != 0){Q.pop();continue;}
        if(nod == 1) continue;
        f[nod] = cost;
        cout << nod << "\n";
        for(i=0;i<a[nod].size();i++)
            Q.push({a[nod][i].S + cost , a[nod][i].F});
        for ( i=2; i<=n; i++)
            cout << f[i] << " ";
            cout<<"\n";
        ok++ ;
        Q.pop();
    }
    for ( i=2; i<=n; i++)
        cout << f[i] << " ";
    return 0;
}