#include <fstream>

#include <utility>
#define x first
#define y second
#include <vector>

#include <queue>

using namespace std;

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

typedef pair <int, int> pii;
const int nmax = 50000, maxint = (1 << 30);
int n, m, xx, yy, costt;
vector <pii> muchii[nmax + 2];

queue <int> dq;

int mincostt[nmax + 2];
int visited[nmax + 2];

int bellmanford(int root){
    for(int i = 1; i <= n; i++){
        mincostt[i] = maxint;
        visited[i] = 0;
    }

    mincostt[root] = 0;
    dq.push(root);

    for(; !dq.empty(); ){
        int node = dq.front(); dq.pop();
        visited[node]++;

        for(auto nxt : muchii[node]){
            if(mincostt[nxt.x] > mincostt[node] + nxt.y){
                mincostt[nxt.x] = mincostt[node] + nxt.y;

                visited[nxt.x]++;
                if(visited[nxt.x] > m){
                    return -1;
                }

                dq.push(nxt.x);
            }
        }
    }

    return 0;
}

int main(){

    in>>n>>m;
    for(int i = 1; i <= m; i++){
        in>>xx>>yy>>costt;
        muchii[xx].push_back(make_pair(yy, costt));
    }

    int okayy = bellmanford(1);

    if(okayy == -1){
        out<<"Ciclu negativ!\n";
    }else{
        for(int i = 2; i <= n; i++)
            out<<mincostt[i]<<" "; out<<"\n";
    }

    return 0;
}