#include <fstream>

using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");
int a[5000][5000],n,i,j,k,m,c[50000],v[50000],x,y,z,ok,mn;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        a[x][y]=z;
    }
    for (i=1;i<=n;i++)
    {
        c[i]=a[1][i];
    }

   v[1]=1;
   ok=1;
   while(ok)
   {
       mn=99999;
       for(i=1;i<=n;i++)
       {
           if(v[i]==0&&mn>c[i])
            {
                mn=c[i];
                k=i;
            }
       }
       if(mn!=99999)
           {
               v[k]=1;
               for(i=1;i<=n;i++)
                {
                        if ( a[k][i]!=0 && i!=k)
                            {
                                if(a[k][i]+c[k]<c[i] || c[i]==0 )
                                {
                                    c[i]=c[k]+a[k][i];

                                }
                            }
                }
            }
        else ok=0;
    }

    for(j=2;j<=n;j++)  g<<c[j]<<" ";
     g<<endl;

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