#include <fstream>

using namespace std;

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

struct muchie{ int x,y,c;}a[50001];

#define INF 5000000

int n,m,D[50001],i,j,x;

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>a[i].x>>a[i].y>>a[i].c;

    D[1]=0;
    for(i=2;i<=n;i++)
        D[i]=INF;

    for(j=1;j<=m;j++)
        for(i=1;i<n;i++)
            if(D[a[j].x]+a[j].c<D[a[j].y])
                D[a[j].y]=D[a[j].x]+a[j].c;

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

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