#include<fstream>
#include<vector>
#include<queue>
struct muchie{
int x,y, c;};
using namespace std;
vector<pair<int,int>> la[50005];
int main(){
    int x,y,c;
    int n,m;
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    f>>n>>m;
    vector<long> d(n+1,1e9);
    vector<int> lung(n+1,-1);
    vector<int> viz(n+1,0);
    for(int i=0;i<m;i++){
        f>>x>>y>>c;
        la[x].push_back({y,c});
    }
    queue<int> q;
    int s=1;
    d[s]=0;
    q.push(s);
    lung[s]=0;
    viz[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        viz[u]=0;
        for(auto m:la[u]){
                if (d[u]+m.second<d[m.first]){
                    d[m.first]=d[u]+m.second;
                    lung[m.first]=lung[u]+1;
                    if(lung[u]>=n) {g<<"Ciclu negativ!"; g.close();return 0;}
                    if(!viz[m.first]){
                        viz[m.first]=1;
                        q.push(m.first);
                    }

                }
        }
    }

        for(int i=2;i<=n;i++)
            g<<d[i]<<" ";



}