#include<vector>
#include<ctime>
#include<fstream>
#define INF 10000000
#define nmax 5002
#define mmax 250000
using namespace std;
ifstream f("dijkstra.in",fstream::in);
ofstream g("dijkstra.out",fstream::out);
int a[nmax][nmax],s[nmax],d[nmax],n,m;
void init()
{
    f>>n;
    int i,j;
    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
      if(i==j)
      a[i][j]=0;
      else
      a[i][j]=INF;
}
void citire()
{
    f>>m;
    int x,y,c,i;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x][y]=c;
    }
}
void generare_dijkstra(int x)
{
    int i,j,min,y;
    for(i=1;i<=n;i++)
    {
        d[i]=a[x][i];
    }
    s[x]=1;
    for(i=1;i<=n-1;i++)
    {
        for(j=1,min=INF;j<=n;j++)
         if(s[j]==0 && d[j]<min)
         {
             min=d[j];
             y=j;
         }
         s[y]=1;
         for(j=1;j<=n;j++)
         if(s[j]==0 && d[y]+a[y][j]<d[j])
         d[j]=d[y]+a[y][j];
    }
}
void tipar()
{
    int i;
    for(i=2;i<=n;i++)
    g<<d[i]<<" ";
}
int main()
{   init();
    citire();
    generare_dijkstra(1);
    tipar();
    f.close();
    g.close();
}