//#include <iostream>
#include<fstream>
#include<vector>
#define mx 50001
#define inf 0x3f3f3f3f
using namespace std;
ifstream fin("dijkstra.in");
ofstream gout("dijkstra.out");
int viz[mx];
int n,m,d[mx],min1,i,j,k;
vector<int> t[mx],v[mx];
void citire()
{
    int i,x,y,c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        t[x].push_back(y);
        v[x].push_back(c);
    }
    fin.close();
}
void dijkstra()
{
    viz[1]=1;
    d[1]=0;
    for(j=1;j<n+1;j++)
    {
        min1=inf;
        k=1;
        for(i=1;i<n+1;i++)
               if(d[i]<min1&&viz[i]==0) {min1=d[i];k=i;}
         viz[k]=1;
        i=0;
        for(i=0;i<t[k].size();i++)
            {
            if(viz[t[k][i]]==0&&d[k]+v[k][i]<d[t[k][i]])
                    { d[t[k][i]]=d[k]+v[k][i]; }//tata[T[k][i]]=k; }
            }

    }
}
int main()
{
    citire();
    for( i=1;i<=n;i++)
        d[i]=inf;
    dijkstra();
    for(i=2;i<n+1;i++)
        if(d[i]==inf) gout<<"0 ";
                    else gout<<d[i]<<" ";
    return 0;
}