#include <iostream>
#include <fstream>

using namespace std;

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

int a[2005][2005],ut[2005],latott[2005],tav[2005],p,q,i,n,m,c,kezd,ok;
const int INF=9999999;
int minimum()
{
    int mini=INF;
    int k=0;
    for(i=1;i<=n;i++)
        if(tav[i]<mini && latott[i]==0)
    {
        mini=tav[i];
        k=i;
    }
    return k;
}
int utkiir(int csp)
{
    if(ut[csp]==0) cout<<csp<<" ";
    else
    {
        utkiir(ut[csp]);
        cout<<csp<<" ";
    }
}
int main()
{
    fin>>n>>m;
    kezd=1;
    for(i=1;i<=m;i++)
    {
        fin>>p>>q>>c;
        a[p][q]=c;
      //  a[q][p]=c;
    }
    for(i=1;i<=n;i++)
    {
        tav[i]=INF;
        ut[i]=0;
        latott[i]=0;
    }
    tav[kezd]=0;
    ok=1;
    while(ok)
    {
        p=minimum();
        if(p!=0)
        {
            latott[p]=1;
            for(i=1;i<=n;i++)
            {
              if(a[p][i]>0 && latott[i]==0)
              {
                  if(tav[i]>tav[p]+a[p][i])
                  {
                      tav[i]=tav[p]+a[p][i];
                      ut[i]=p;
                  }
              }
            }
        }
        else ok=0;
    }
  //  for(i=1;i<=n;i++) cout<<ut[i]<<" ";

 /*   for(i=1;i<=n;i++)
    {
        utkiir(i);
        cout<<"\n";
    }  */

    for(i=2;i<=n;i++)
        if(tav[i]==INF) fout<<0<<"  ";
    else
        fout<<tav[i]<<" ";
}