#include <cstdio>
#include <queue>
#include <vector>
#define nmax 50005
using namespace std;

struct muchie
{
    int c,d;
};

queue <muchie> q;
vector <muchie> g[nmax];
int updateCount[nmax];
bool inQueue[nmax];
int cost[nmax];
int n,m;
bool negativeCycleFlag;

muchie mkmuc(int d,int c)
{
    muchie nou;
    nou.c = c;
    nou.d = d;
    return nou;
}

bool update(int nod,int newCost)
{
    bool updated = false;
    if (cost[nod] > newCost)
    {
        cost[nod] = newCost;
        updated = true;
        updateCount[nod]++;
    }
    if (updateCount[nod] >= n-1) negativeCycleFlag = true;
    return updated;
}

void bellmanford(int start)
{
    cost[start] = 0;
    q.push(mkmuc(start,0));
    inQueue[start] = true;
    while (!q.empty())
    {
        if (negativeCycleFlag) return;

        muchie nod = q.front(); q.pop();
        inQueue[nod.d] = false;

        for (vector <muchie> :: iterator it = g[nod.d].begin(); it != g[nod.d].end(); it++)
        {
            muchie muc = *it;
            bool updated = update(muc.d,muc.c+cost[nod.d]);

            if (!inQueue[muc.d] && updated)
            {
                q.push(mkmuc(muc.d,muc.c+cost[nod.d]));
                inQueue[muc.d] = true;
            }
        }
    }
}

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

    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++) cost[i] = 100000000;

    for (int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        g[a].push_back(mkmuc(b,c));
    }

    bellmanford(1);

    if (negativeCycleFlag)
    {
        printf("Ciclu negativ!");
    }
    else
    {
        for (int i=2;i<=n;i++) printf("%d ",cost[i]);
    }

}