#include<fstream>

using namespace std;

#define xn 50001
#define xm 250001
#define inf 0x3f3f3f

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m,d[xn],e[xm][3];

void bellman()
{
     int x,y,c,i,nr,ok;
     
     memset(d,inf,sizeof(d));
     
     d[1]=0;
     
     for(ok=nr=1;ok && nr<n;nr++)
        for(ok=i=0;i<m;i++)
        {
           x=e[i][0];
           y=e[i][1];
           c=e[i][2];
           if(d[y]>d[x]+c)
             d[y]=d[x]+c,ok=1;
        }
}

int main()
{
    int i;
    fin>>n>>m;
    for(i=0;i<m;i++)
      fin>>e[i][0]>>e[i][1]>>e[i][2];
    
    bellman();
    
    for(i=2;i<=n;i++)
      fout<<d[i]<<' ';
    fout<<'\n';
    
    fout.close();
    return 0;
}