//bellman ford
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
const int INF = 1e9;
int n,m;
struct muchie {int a,b,cost;};
vector<int> d;
vector<muchie> M;
bool bellman(int s) {
    d[s] = 0;
    bool schimbare = false;
    for (int i=1;i<=n;i++) {
        for (auto [u,v,cost] : M)
            if (d[u] + cost < d[v]) {
                d[v] = d[u] + cost;
                schimbare = true;
            }
        if (!schimbare) return true;
        if (i==n)return false;
    }
    return true;
}
int main() {
    fin>>n>>m;
    d.assign(n+1,INF);
    for (int i=1;i<=m;i++) {
        int x,y,z;
        fin>>x>>y>>z;
        M.push_back({x,y,z});
    }
    if (bellman(1))
        for (int i=2;i<=n;i++)fout<<d[i]<<' ';
    else
        fout<<"Ciclu negativ!";

    return 0;
}

//catun
// #include <bits/stdc++.h>
// using namespace std;
// ifstream fin ("catun.in");
// ofstream fout ("catun.out");
// const int INF = 1e9;
// int n,m,k;
// vector<vector<pair<int,int>>> M;
// vector<int> tata,d,extra,reprez;
// void djikstra(vector <int> starts) {
//     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>Q;
//     for (auto fort : starts) {
//         reprez[fort] = fort;
//         d[fort] = 0;
//         Q.push({d[fort],fort});
//     }
//     while (!Q.empty()) {
//         auto [dist_u, u] = Q.top();
//         Q.pop();
//         for (auto [v, cost] : M[u])
//             if (d[u] + cost < d[v]) {
//                 d[v] = d[u] + cost;
//                 reprez[v] = reprez[u];
//                 Q.push({d[v],v});
//             }
//         else if (d[u] + cost == d[v] && reprez[u] < reprez[v]) reprez[v] = reprez[u];
//     }
// }
// int main() {
//     fin>>n>>m>>k;
//     tata.assign(n+1,0);
//     d.assign(n+1,INF);
//     extra.resize(k+1);
//     reprez.assign(n+1,INF);
//     M.resize(n+1);
//     for (int i=1;i<=k;i++) fin>>extra[i];
//     for (int i=1;i<=m;i++) {
//         int x,y,z;
//         fin>>x>>y>>z;
//         M[x].push_back({y,z});
//         M[y].push_back({x,z});
//     }
//     djikstra(extra);
//     for (int i=1;i<=n;i++) {
//         if (d[i] == INF || reprez[i] == i) fout<<0<<' ';
//         else fout<<reprez[i]<<' ';
//     }
//     return 0;
// }

//3
// #include <bits/stdc++.h>
// using namespace std;
// ifstream fin ("date.in");
// #define rep(a,b) for(int i=a;i<=b;i++)
// const int INF = 1e9;
// vector<vector<pair<int,int>>> M;
// vector <int> d,tata;
// int n,m,start,finish;
// void djikstra(int s) {
//     d[s] = 0;
//     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q;
//     Q.push({d[s], s});
//     while (!Q.empty()) {
//         auto [dist_u, u] = Q.top();
//         Q.pop();
//         if (dist_u > d[u]) continue;
//         for (auto [v, cost] : M[u])
//             if (d[u] + cost < d[v]) {
//                 d[v] = d[u] + cost;
//                 tata[v] = u;
//                 Q.push({d[v],v});
//             }
//     }
// }
// int main() {
//     fin>>n>>m;
//     M.resize(n+1);
//     d.assign(n+1,INF);
//     tata.assign(n+1,0);
//     rep (1,m) {
//         int x,y,z;
//         fin>>x>>y>>z;
//         M[x].push_back({y,z});
//     }
//     fin>>start>>finish;
//     djikstra(start);
//     while (finish) {
//         cout<<finish<<' ';
//         finish = tata[finish];
//     }
//     return 0;
// }
// #include <bits/stdc++.h>
// using namespace std;
// ifstream fin("date.in");
// typedef long long ll;
// #define rep(a,b) for(int i=a;i<=b;i++)
// const ll INF = 1e18;
// int n,m,k,s;
// vector<ll> d;
// vector<int> tata,control;
// vector<vector<pair<int,int>>> M;
// void djikstra(int s) {
//     d[s] = 0;
//     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q;
//     Q.push({d[s],s});
//     while (!Q.empty()) {
//         auto [dist_u, u] = Q.top();
//         Q.pop();
//         if (dist_u > d[u])continue;
//         for (auto [v, cost] : M[u])
//             if (d[u] + cost < d[v]) {
//                 d[v] = d[u] + cost;
//                 tata[v] = u;
//                 Q.push({d[v],v});
//             }
//     }
// }
// void afiseazainvers(int i) {
//     if (i!=0) {
//         afiseazainvers(tata[i]);
//         cout<<i<<' ';
//     }
// }
// int main() {
//     fin>>n>>m;
//     d.assign(n+1,INF);
//     tata.assign(n+1,0);
//     M.resize(n+1);
//     rep(1,m) {
//         int x,y,z;
//         fin>>x>>y>>z;
//         M[x].push_back({y,z});
//         M[y].push_back({x,z});
//     }
//     fin>>k;
//     control.resize(k+1);
//     rep(1,k) fin>>control[i];
//     fin>>s;
//     djikstra(s);
//     int index=0, drum = 1e9;
//     rep(1,k)
//         if (d[control[i]] < drum) {
//             drum = d[control[i]];
//             index = control[i];
//         }
//     cout<<index<<'\n';
//     afiseazainvers(index);
//     return 0;
// }

//dijghistra
// #include <bits/stdc++.h>
// using namespace std;
// ifstream fin ("dijkstra.in");
// ofstream fout ("dijkstra.out");
// typedef long long ll;
// const ll INF = 1e18;
// #define rep(a,b) for(int i=a;i<=b;i++)
// vector<vector<pair<int,int>>> M;
// vector<ll> d;
// int n,m;
// void djikstra(int s) {
//     d[s] = 0;
//     priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>>> Q;
//     Q.push({d[s],s});
//     while (!Q.empty()) {
//         auto [dist_u, u] = Q.top();
//         Q.pop();
//         if (dist_u > d[u]) continue;
//         for (auto [v, cost] : M[u])
//             if (d[u] + cost < d[v]) {
//                 d[v] = d[u] + cost;
//                 Q.push({d[v],v});
//             }
//     }
// }
// int main() {
//     fin>>n>>m;
//     M.resize(n+1);
//     d.assign(n+1,INF);
//     rep(1,m) {
//         int x,y,z;
//         fin>>x>>y>>z;
//         M[x].push_back({y,z}); // v cost
//     }
//     djikstra(1);
//     rep(2,n) {
//         if (d[i] == INF) fout<<0<<' ';
//         else fout<<d[i]<<' ';
//     }
//     return 0;
// }