#include <fstream>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int d[10000],t[10000],n,m,Min;
int c[10000][10000];
int r,s[10000];
void citire()
{
    int i,j,k,cost;
    f>>n>>m;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(i!=j)
                c[i][j]=10000;
    for(k=1; k<=m; k++)
    {
        f>>i>>j>>cost;
        c[i][j]=c[j][i]=cost;
    }
}
void dijkstra(int r)
{
   s[r]=1;
   int i;
   for(i=1;i<=n;i++)
    if(i!=r)
   {
       d[i]=c[i][r];
       t[i]=r;
   }
   d[r]=0;
   t[r]=0;
   int k,j;
   for(k=1;k<=n;k++)
   {
       Min=10000;
       for(j=1;j<=n;j++)
        if(Min>d[j] && s[j]==0)
       {
           i=j;
           Min=d[j];
       }
       s[i]=1;
       for(j=1;j<=n;j++)
        if(d[j]>d[i]+c[i][j])
       {
           d[j]=d[i]+c[i][j];
           t[j]=i;
       }
   }
}
void afislant(int i)
{
    if(t[i]>0)
        afislant(t[i]);
    g<<i<<" ";
}
int main()
{
    citire();
    dijkstra(1);
    for(int i=1;i<=n;i++)
        if(i!=1)
        g<<d[i]<<" ";
    return 0;
}