#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()
{
    queue<edge> Q;
    crt.nod = 1;
    crt.val = 0;
    Q.push(crt);

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

            if (mn[now] > val + crt.val)
            {
                nr[now]++;
                if (nr[now]>=n)
                {
                    g<<"Ciclu negativ!";
                    return 0;
                }
                mn[now] = val+crt.val;
                if (!inQ[now])
                {
                    edge crt2;
                    crt2.nod = now;
                    crt2.val = val+crt.val;
                    Q.push(crt2);
                    inQ[now] = 1;
                }
            }
        }
        inQ[crt.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;
}