#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector <pair<int,int>> v[50001];
queue <int> q;
bool ing[50001];
int n,m,best[50001],nr[50001],flag=1;
const int inf=2000000000;
void bellmanford(int nod)
{
    for(int i=1;i<=n;i++)
        best[i]=inf;
    q.push(nod);
    ing[nod]=true;
    best[nod]=0;
    nr[nod]=1;
    while(!q.empty()){
        int pr=q.front();
        q.pop();
        ing[pr]=false;
        for(int i=0;i<v[pr].size();i++){
            int y=v[pr][i].first;
            int c=v[pr][i].second;
            if(best[pr]+c<best[y]){
                nr[y]++;
                best[y]=best[pr]+c;
                if(!ing[y]){
                    ing[y]=true;
                    q.push(y);
                }
            if(nr[y]==n){
                flag=0;
                g<<"Ciclu negativ!";
                return;
            }
            }

        }
    }
}
int main()
{
    int a,b,c;
    f>>n>>m;
    for(int i=1;i<=m;i++){
        f>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
    }
    bellmanford(1);
    if(flag==1)
        for(int i=2;i<=n;i++)
           g<<best[i]<<' ';
    return 0;
}