#include <iostream>
#include <fstream>
#include <queue>
#include <cstdlib>

using namespace std;
const int maxn = 5e4+5, inf = 0x3f3f3f3f;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

typedef struct nod {
    int i, c;
    nod *next;
} *pNod;
pNod v[maxn];

void add(int x, int y, int z) {
    pNod p = new nod;
    p -> i = y;
    p -> c = z;
    p -> next = v[x];
    v[x] = p;
}

int ans[maxn];
int done[maxn];
bool is[maxn];

/*class pqc
{
public:
    bool operator () (int x, int y) {
        return (ans[x] > ans[y]);
    }
};*/

inline void negative(){
    g << "Ciclu negativ!";
    exit(0);
}

int n, m;
queue <int> q;
void bf()
{
    int i, j;
    bool ok = false;

    for(i = 2; i <= n; i ++) {
        ans[i] = inf;
    }

        ok = false;
        q.push(1);
        done[1] ++;
        while(!q.empty())
        {
            j = q.front();
            is[j] = false;
            q.pop();
            for(pNod p = v[j]; p != NULL; p = p -> next)
            {
                if(ans[j] + (p -> c) < ans[p -> i])
                {
                    if(done[j] >= n)
                    {
                        negative();
                    }
                    ans[p -> i] = ans[j] + (p -> c);
                    if(is[p -> i] == true)
                    {
                        continue;
                    }
                    done[p -> i] ++;
                    q.push(p -> i);
                    is[p -> i] = true;
                }
            }
        }


    if(ok == true)
    {
        negative();
    }
    if(ok == false)
    {
        return;
    }

}

int main()
{
    int i, x, y, z;
    f >> n >> m;

    for(i = 1; i <= m; i ++) {
        f >> x >> y >> z;
        add(x, y, z);
    }

    bf();

    for(i = 2; i <= n; i ++) {
        if(ans[i] == inf)
            g << "0 ";
        else
            g << ans[i] << ' ';
    }

    f.close();
    g.close();
    return 0;
}