#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int d[1001],t[1001];
const int INF = 1e9;
bitset<1001> viz;
int n,m,a[1001][1001];
void citire()
{
    int x,y,i,c;
    fin>>n>>m;
    for(i=1;i<=m;i+=1)
    {
        fin>>x>>y>>c;
        a[x][y]=c;
    }
}
void prelucrare()
{
    int i,j;
    for(i=1;i<=n;i+=1)
        for(j=1;j<=n;j+=1)
            if(i!=j and a[i][j]==0)
                a[i][j]=INF;
}
void dijkstra(int v)
{
    int mini,kk,j,k,i;
    for(i=1;i<=n;i+=1)
    {
        d[i]=a[v][i];
        if(d[i]<INF)
            t[i]=v;
    }
    for(kk=1;kk<n;kk+=1)
    {
        mini=INF;
        for(j=1;j<=n;j+=1)
            if(d[j]<mini and !viz[j])
            {
                mini=d[j];
                k=j;
            }
        viz[k]=1;
        for(i=1;i<=n;i+=1)
            if(!viz[i])
                if(d[i]>d[k]+a[k][i])
                    d[i]=d[k]+a[k][i],t[i]=k;
    }
    for(i=2 ;i<=n;i+=1)
        fout<<d[i]<<' ';
}
int main()
{
    citire();
    prelucrare();
    dijkstra(1);
    return 0;
}