#include <bits/stdc++.h>
#define Nmax 50002
#define oo 0x3f3f3f3f
#define pb(x) push_back(x)
FILE *fin  = freopen("bellmanford.in", "r", stdin);
FILE *fout = freopen("bellmanford.out", "w", stdout);

using namespace std;
int n, m, dp[Nmax], cnt[Nmax];
bool neg_cycle = false;
vector <pair <int, int> > G[Nmax];
queue <int> Q;
bitset <Nmax> b;
void read()
{
    int u, v, w;
    scanf("%d %d", &n, &m);
    while(m --)
    {
        scanf("%d %d %d", &u, &v, &w);
        G[u].pb(make_pair(v, w));
    }
}
void solve()
{
    unsigned short u;

    memset(dp, oo, sizeof(dp));
    dp[1] = 0;
    b.set(1);
    Q.push(1);
    ++ cnt[1];

    while(!Q.empty() && !neg_cycle)
    {
        u = Q.front();
        Q.pop();
        b.set(1, 0);
        vector < pair <int, int> >::iterator it;
        for(it = G[u].begin(); it != G[u].end(); ++ it)
        {
            if(dp[u] < oo)
                if(dp[it->first] > dp[u] + it->second)
            {
                dp[it->first] = dp[u] + it->second;
                if(!b.test(it->first))
                {
                    if(cnt[it->first] == n)
                    {
                        puts("Ciclu negativ!");
                        exit(0);
                    }
                    else
                    {
                        Q.push(it->first);
                        b.set(it->first);
                        ++ cnt[it->first];
                    }
                }
            }
        }
    }
}
void write()
{
    for(int i = 2; i <= n; ++ i)
        printf("%d ", dp[i]);
    printf("\n");
}
int main()
{
    read();
    solve();
    write();
    return 0;
}