#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>

#define pb push_back
#define mp make_pair
#define Nmax 50001
#define INF 10000000

using namespace std;

vector< pair <int, int> > G[Nmax];
queue <int> q;
int n,m,i,d[Nmax],ap[Nmax];

void BellmanFord()
{
    int x,mih;
    d[1]=0;
    q.push(1);
    ap[1]=1;
    for (i=2;i<=n+2;++i)
        d[i]=INF;
    while (!q.empty())
    {
        x=q.front();
        q.pop();
        mih = G[x].size();
        for (i=0; i<mih;i++)
            if (d[x]+G[x][i].second<d[G[x][i].first])
            {
                d[G[x][i].first]=d[x]+G[x][i].second;
                q.push(G[x][i].first);
                ap[G[x][i].first]++;
                if(ap[G[x][i].first]>n)
                {
                    printf("Ciclu negativ!\n");
                }
            }
    }
    for (i=2;i<=n;i++)
        printf("%d ",d[i]);
    printf("\n");
}


int main()
{
    int a, b, c;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d",&n, &m);
    for (i=1;i<=m;i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        G[a].pb(mp(b,c));
    }
    BellmanFord();
    fclose(stdin);
    fclose(stdout);
    return 0;
}