#include <fstream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define Nmax 50001
#define pb push_back
using namespace std;

ofstream g("bellmanford.out");

int n,m,nr[Nmax],mn[Nmax];
bool inQ[Nmax];

struct edge{
    int nod,val;
}crt;

vector<edge> V[Nmax];


bool bellmanford()
{
    int nod;
    queue<int> Q;
    Q.push(1);

    memset(mn,0x3f,sizeof(mn));
    mn[1] = 0;
    while (!Q.empty())
    {
        nod = Q.front();
        Q.pop();
        for (int i=0;i<V[nod].size();i++)
        {
            int now = V[nod][i].nod;
            int val = V[nod][i].val;

            if (mn[now] > mn[nod] + val)
            {
                nr[now]++;
                if (nr[now]>=n)
                {
                    g<<"Ciclu negativ!\n";
                    return 0;
                }
                mn[now] = mn[nod] + val;
                if (!inQ[now])
                {
                    Q.push(now);
                    inQ[now] = 1;
                }
            }
        }
        inQ[nod] = 0;
    }

    return 1;
}


int main()
{
    freopen("bellmanford.in","r",stdin);

    scanf("%d%d",&n,&m);

    for (int i=1;i<=m;i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        crt.nod = y;
        crt.val = c;
        V[x].pb(crt);
    }

    if (!bellmanford())
        return 0;

    for (int i=2;i<=n;i++)
        g<<mn[i]<<' ';


    return 0;
}