#include <fstream>

using namespace std;

long int v[50005],minim;
long int i,j,x,y,z,poz,nr,t[50005],n,m,a[20005][20005];

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for (i=1;i<=m;i++) {
           f>>x>>y>>z;
           a[x][y]=z;
           if (x==1) v[y]=z;
    }
    t[1]=1;
    for (i=2;i<=n;i++)
    if (v[i]==0) v[i]=300000;
    nr=1;
    while (nr<n) {
           nr++;
           minim=300000;
           for (i=2;i<=n;i++)
           if (v[i]<minim &&t[i]==0) {minim=v[i];poz=i;}
           t[poz]=1;
           for (i=2;i<=n;i++)
           if (v[i]>a[1][poz]+a[poz][i] &&a[1][poz]!=0 &&a[poz][i]!=0) v[i]=a[1][poz]+a[poz][i];
    }

    for (i=2;i<=n;i++)
    g<<v[i]<<' ';
    f.close();
    g.close();
    return 0;
}