#include <iostream>
#include<vector>
#include<queue>
#include<string>
#include<fstream>

using namespace std;

class graf
{
    int n,m,*frecventa,*distanta,ok;
    bool *marcheaza;
    queue<int> coada;
	ifstream f;
	ofstream g;
    struct muchie
    {
        int nod,cost;
    };
    vector<muchie> *lg;	//load graf
    
public:
    graf(int x,string fin,string fout)
    {
		ifstream f("bellmananford.in");
		ofstream g("bellmanford.out");
		coada.push(1);
        marcheaza[1]=1;
        for(int i=1;i<=n;i++)
        {
            distanta[i]=1<<30;
            frecventa[i]=0;
        }
        distanta[1]=0;
       
        marcheaza = new bool[x];
        frecventa = new int[x];
        lg = new vector<muchie>[x];
        distanta = new int[x];
    }
  
    void create()
    {
 
        int a;
        muchie b;
        f>>n>>m;
        
        for(int i=1;i<=m;i++)
        {
            f>>a>>b.nod>>b.cost;
            lg[a].push_back(b);
        }
    }
    void bellmanford()
    {
        int x;
        ok=1;
        while(ok && !coada.empty())
        {
            x = coada.front();
            coada.pop();
            marcheaza[x]=0;
            for(int i=0;i<lg[x].size();i++)
            {
                
                if(distanta[x]+lg[x][i].cost<distanta[lg[x][i].nod])
                {
                    distanta[lg[x][i].nod]=distanta[x]+lg[x][i].cost;
                    if(!marcheaza[lg[x][i].nod])
                    {
                        if(frecventa[lg[x][i].nod]>n)
                            ok=0;
                        else
                        {
                            coada.push(lg[x][i].nod);
                            marcheaza[lg[x][i].nod]=1;
                            frecventa[lg[x][i].nod]++;
                        }
                    }
                }
            }
 
        }
        if(ok==0)
            g<<"Ciclu negativ!"<<endl;
        else
        {
            for(int i=2;i<=n;i++)
                g<<distanta[i]<<" ";
        }
    }
    
};
int main()
{
    graf X(50001,"bellmanford.in","bellmanford.out");
    X.create();
    X.bellmanford();
    return 0;
}