#include <fstream>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int maxim=1500000;
int a[5000][5000],d[5000],t[5000],p[5000],n,m,s,i,j,cost;

void dijkstra(int s)
{ int i,j,k,minim;
  for(i=1;i<=n;i++)
     { d[i]=a[s][i];
       if(i!=s && d[i]!=maxim) t[i]=s;
     }
  p[s]=1;
  for(k=1;k<n;k++)
   { minim=maxim;
     for(i=1;i<=n;i++)
       if(!p[i] and d[i]<minim) minim=d[i],j=i;

     for(i=1;i<=n;i++)
       if(!p[i])
       if(d[i]>d[j]+a[j][i])
	 { d[i]=d[j]+a[j][i];
	   t[i]=j;
	 }
     p[j]=1;
   }
}

void drum(int i)
{ if(t[i]!=0) drum(t[i]);
  g<<i<<" ";
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
      if(i==j) a[i][j]=0;
      else a[i][j]=maxim;
    while(m)
    {
        f>>i>>j>>cost;
        a[i][j]=cost;
    m--;
    }
   dijkstra(1);
   for(i=2;i<=n;i++)
   {
    if(d[i]==1500000) g<<"-1"<<" ";
    else
     g<<d[i]<<" ";
   }

    return 0;
}