#include <iostream>
#include <fstream>
using namespace std;
const int INF=1010101001;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,a[1000][1000];
int c[10000],dist[10000],rep[10000];
bool viz[10000];
void BF(int v)
{
    int k=0;
    bool ciclu=false;
    for(int i=1; i<=n; i++)
        dist[i]=INF;
    dist[v]=0;
    c[++k]=v;
    viz[v]=true;
    int i;
    for(i=1; i<=k and !ciclu; i++)
    {
        int nc=c[i];
        viz[nc]=0;
        if(rep[nc]>=n)
            ciclu=true;
        for(int j=1; j<=n; ++j)
            if(a[nc][j] and dist[j]>dist[nc]+a[nc][j])
            {
                dist[j]=dist[nc]+a[nc][j];
                rep[j]++;
                if(!viz[j])
                {
                    c[++k]=j;
                    viz[j]=true;
                }
            }
    }
}

int main()
{
int start=1;
f>>n>>m;
int x,y,c;
while(m--)
{
    f>>x>>y>>c;
    a[x][y]=c;
}
BF(start);
for(int i=2;i<=n;i++)
    g<<dist[i]<<' ';
    return 0;
}