#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int a[510][510],n,m,A,B,C;
#define infinit 20010
int viz[510],d[510],mini,poz;

void citire()
{   f>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) if( i != j ) a[i][j]=infinit;
    while(m)
    {   f>>A>>B>>C; a[A][B]=C; m--;
    }
}

/*void afis()
{   for(int i=1;i<=n;i++)
    {   for(int j=1;j<=n;j++) g<<a[i][j]<<" ";
        g<<'\n';
    }
}*/

void dijkstra(int X)
{   viz[X]=1;
    for(int i=1;i<=n;i++)
    {   d[i]=a[X][i];
        ///if( i != X ) if( d[i] < infinit ) tata[i]=X;
    }
    for(int i=1;i<=n-1;i++)
    {   mini=infinit;
        for(int j=1;j<=n;j++)
            if( viz[j] == 0 and mini > d[j] ) {mini=d[j]; poz=j;}
        viz[poz]=1;
        for(int j=1;j<=n;j++)
            if( viz[j] == 0 and d[j] > d[poz]+a[poz][j] )
            {   d[j]=d[poz]+a[poz][j];
                ///tata[j]=poz;
            }
    }
}

int main()
{   citire();

    dijkstra(1);

    for(int i=2;i<=n;i++) g<<d[i]<<" ";

g.close();
return 0;
}