#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int N,M;
#define infint 200009
struct node
{
    int nod;
    int distanta;
};
deque < node > graf[50005];
deque <int> ordine;
int distanta[50005];
int vizitat[50005];
void citie()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        graf[x].push_back({y,z});
    }
    for(int i=2;i<=N;i++)
    {
        distanta[i]=infint;
    }
    vizitat[1]=1;
}
void dijkstra()
{
    ordine.push_back(1);
    while(!ordine.empty())
    {
        int nod=ordine.back();
        int di=distanta[nod];
        ordine.pop_back();
        cout<<nod<<endl;
        for(node vecin : graf[nod])
        {
            int nod_nou=vecin.nod;
            cout<<' '<<nod_nou<<endl;
            int di_nou=vecin.distanta;
            int di_actuala=distanta[nod_nou];
            if(di_actuala==infint)
            {
                distanta[nod]=di_nou+di;
            }
            else
            {
                if(di_nou+di<di_actuala)
                    distanta[nod]=di_nou+di;
            }
            if(vizitat[nod_nou]==0)
            {
                vizitat[nod_nou]=1;
                ordine.push_back(nod_nou);
            }


        }
    }
}
int main()
{
    citie();
    dijkstra();
    for(int i=2;i<=N;i++)
    {
        fout<<distanta[i];
    }
}