#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

FILE *fin, *fout;

#define MAXN 50000
#define MAXM 250000

struct at  {
    int vec;int cost;
};

int n, m;
std::vector <at> v[MAXN + 1];
int dp[MAXN + 1];
std::queue <int> q;
bool viz[MAXN + 1];
int hm[MAXN + 1];

inline bool belfor()  {
    q.push(1);
    viz[1] = hm[1] = 1;
    while(!q.empty())  {
        int el = q.front();
        q.pop();
        viz[el] = 0;
        for(auto &x : v[el])  {
            if(dp[x.vec] > dp[el] + x.cost)  {
                dp[x.vec] = dp[el] + x.cost;
                if(viz[el] == 0)  {
                    viz[el] = 1;
                    hm[el]++;
                    if(hm[el] >= n)  {
                        fprintf(fout, "Ciclu negativ!\n");
                        return 1;
                    }
                    q.push(x.vec);
                }
            }
        }
    }
    return 0;
}

#define inf 1000000000

int main()  {
    fin = fopen("bellmanford.in", "r");
    fout = fopen("bellmanford.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(int i = 1;i <= m;i++)  {
        int x, y, c;
        fscanf(fin, "%d%d%d", &x, &y, &c);
        v[x].push_back({y, c});
    }
    for(int i = 1;i <= n;i++)
        dp[i] = inf;
    dp[1] = 0;
    if(belfor())  {
        return 1;
    }
    for(int i = 2;i <= n;i++)
        fprintf(fout, "%d ", dp[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}