#include <cstdio>
#include <iostream>
#include <fstream>
using namespace std;
int a[10001][10001],d[1001],s[1001],p[1001],n,m;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int const MAX=20000;
void init()
{
    int i,j;
    for(int i=1; i<=101; i++)
        for(int j=1; j<=101; j++)
        {
            a[i][j]=20000;
            a[i][i]=0;
        }
}
void citire()
{
    int i;
    int x,y,c;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>x>>y>>c;
        a[x][y]=c;
    }
}
void generare(int x)
{
    int i,j,min,y;
    s[x]=1;
    for(i=1; i<=n; i++)
    {
        d[i]=a[x][i];
        if(i!=x && d[i]<MAX)
            p[i]=x;
    }
    for(i=1; i<=n-1; i++)
    {
        for(j=1,min=MAX; j<=n; j++)
            if(s[j]==0 && d[j]<min)
            {
                min=d[j];
                y=j;
            }
        s[y]=1;
        for(j=1; j<=n; j++)
            if(s[j]==0 && d[j]>d[y]+a[y][j])
            {
                d[j]=d[y]+a[y][j];
                p[j]=y;
            }
    }
}
void drum(int i)
{
    if(p[i]!=0)
        drum(p[i]);
    out<<i<<" ";
}
void afisare(int x)
{
    int i;
    for( i=1; i<=n; i++)
    {
        if(i!=x)
            if(p[i]!=0)
            out<<d[i]<<" ";
        else
            out<<0<<" ";
    }
}
int main()
{
    init();
    citire();
    generare(1);
    afisare(1);
    return 0;
}