//classic
#include <iostream>
#include <fstream>
using namespace std;
short M[2][20000][20000],Cost[50001],Parinte[50001],n,m;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
void adancime(int nod)
{
    int i;
    for (i=1;i<=M[0][nod][0];i++)
    {
        cout<<M[0][nod][i]<<" ";
        if (M[1][nod][i]+Cost[nod]<Cost[M[0][nod][i]]||Cost[M[0][nod][i]]==0)
        {
            Parinte[M[0][nod][i]]=nod;
            Cost[M[0][nod][i]]=M[1][nod][i]+Cost[nod];
            adancime(M[0][nod][i]);
            //cout<<'a';
        }
    }
}
int main()
{
    f>>n>>m;
    int i,a,b,cost;
    for (i=1;i<=m;i++)
    {
        f>>a>>b>>cost;
        M[0][a][0]++;
        M[0][a][M[0][a][0]]=b;
        M[1][a][M[0][a][0]]=cost;
    }
    adancime(1);

    for (i=2;i<=n;i++) g<<Cost[i]<<" ";
}