#include <fstream>
#include <queue>
#include <cstring>
#include <vector>
#define NM 100010
#define node second
#define cost first
#define INF 1999999999

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

typedef pair<int, int> PI;
priority_queue< PI, vector< PI >, greater<PI> > Q;

vector<int> Drum;
vector<PI> G[NM];

int N,M;
int i,j;
int a,b;
int c;
int S[3];
int D[3][NM];
int ANS;
int CANS=INF;

void DoDijkstra (int P)
{
    int i;
    vector<PI>::iterator it;
    int node,cost;

    for (i=1; i<=N; i++)
        D[P][i]=INF;

    D[P][S[P]]=0;
    Q.push(make_pair(0,S[P]));

    while (!Q.empty())
    {
        node=Q.top().node;
        cost=Q.top().cost;
        Q.pop();

        if (D[P][node]!=cost) continue;

        for (it=G[node].begin(); it!=G[node].end(); ++it)
            if (cost+it->cost<D[P][it->node])
            {
                D[P][it->node]=cost+it->cost;
                Q.push(make_pair(D[P][it->node],it->node));
            }
    }

    return;
}

void Reconstruct (int P)
{
    Drum.clear();
    int node=ANS;
    int cost;
    vector<PI>::iterator it;

    while (node!=S[P])
    {
        Drum.push_back(node);
        cost=D[P][node];
        for (it=G[node].begin(); it!=G[node].end(); ++it)
            if (cost-it->cost==D[P][it->node])
            {
                node=it->node;
                break;
            }
    }

    g << Drum.size()+1 << ' ';

    for (int i=0; i<Drum.size(); i++)
        g << Drum[i] << ' ';

    g << S[P] << '\n';

    return;
}

int main ()
{
    f >> N >> M;
    /*for (i=0; i<3; i++)
        f >> S[i];*/
    S[0]=1;

    for (i=1; i<=M; i++)
    {
        f >> a >> b >> c;
        G[a].push_back(make_pair(c,b));
       // G[b].push_back(make_pair(c,a));
    }


        DoDijkstra(0);

    /*for (i=1; i<=N; i++)
    {
        if (D[0][i]>=INF || D[1][i]>=INF || D[2][i]>=INF) continue;
        if (D[0][i]+D[1][i]+D[2][i]<CANS)
        {
            CANS=D[0][i]+D[1][i]+D[2][i];
            ANS=i;
        }
    }

    g << CANS << '\n';
    for (i=0; i<3; i++)
        Reconstruct(i);*/

    for (i=2; i<=N; i++)
        g << D[0][i] << ' ';

    f.close();
    g.close();
    return 0;
}