#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];
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()
{
    int u;

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

    while(!Q.empty())
    {
        u = Q.front();
        Q.pop();
        b.reset(u);
        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] < oo ? dp[i] : 0);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}