#include <fstream>
#include <vector>
#include <bitset>
#include <queue>

using namespace std;
const int INF = 21e8;
const int NMAX = 50002;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

struct muchii
{
    int nod, cost;
};
vector < vector < muchii > > v;
int ans[NMAX], cnt[NMAX], n;
bool bellmanFord()
{
    bitset < NMAX > in_coada;
    queue < int > q;
    q.push(1);
    in_coada[1] = true;
    ans[1] = 0;
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        for(muchii var : v[now])
        {
            if(ans[now] + var.cost < ans[var.nod])
            {
                ans[var.nod] = ans[now] + var.cost;
                if(!in_coada[var.nod]) ///dc nu l-am accesat pana acm
                {
                    q.push(var.nod);
                    in_coada[var.nod] = true;
                    cnt[var.nod]++;
                    if(cnt[var.nod] > n)
                        return false;
                }
            }
        }
        in_coada[now] = false;
    }
    return true;
}
int main()
{
    int m, a, b, cost;
    cin >> n >> m;
    v.resize(n + 1); ///lista de adiacente
    for(int i = 1; i <= m; i++)
    {
        cin >> a >> b >> cost;
        v[a].push_back({b, cost});
        //v[b].push_back({a, cost});
    }
    for(int j = 1; j <= n; j++)
        ans[j] = INF;
    if(bellmanFord() == false)
    {
        cout << "Ciclu negativ!";
        return 0;
    }
    for(int i = 2; i <= n; i++)
        cout << ans[i] << " ";
    return 0;
}
/*
5 10
1 2 2
1 3 3
1 4 4
1 5 5
2 3 4
2 4 5
2 5 1
3 4 1
3 5 2
4 5 3

0 2 3 4 3
2 0 3 4 1
3 3 0 1 2
4 4 1 0 3
3 1 2 3 0

5 6
1 2 -1
2 3 -2
3 4 1
4 1 2
2 5 4
5 3 -3

5 6
1 2 1
2 3 2
3 4 1
4 1 2
2 5 4
5 3 3

*/