#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;
    string in, out;
    struct muchie
    {
        int nod,cost;
    };
    vector<muchie> *lg;   //load graf
     
public:
    graf(string fin,string fout)
    {
		in = fin;
		out = fout;

        ifstream f(in);

		f >> n >> m;

		marcheaza = new bool[n+1];
        frecventa = new int[n+1];
        lg = new vector<muchie>[n+1];
        distanta = new int[n+1];
		
		int a;;
		muchie b;

		 for(int i=1;i<=m;i++)
        {
            f>>a>>b.nod>>b.cost;
            lg[a].push_back(b);
        }
		 f.close();
    }
   

    void bellmanford()
    {
		ofstream g(out);

        int x;

		coada.push(1);
        marcheaza[1]=1;

        for(int i=1;i<=n;i++)
        {
            distanta[i]=1<<30;
            frecventa[i]=0;
			marcheaza[i]=0;
        }
        distanta[1]=0;

        while(!coada.empty())
        {
            x = coada.front();
            for(int i=0;i<lg[x].size();i++)
            {
				int nod = lg[x][i].nod;
				int cost = lg[x][i].cost;
                 
                if(distanta[x] + cost < distanta[nod])
                {
                    distanta[nod] = distanta[x] + cost;
                    if(!marcheaza[nod])
                    {
                        if(frecventa[nod]>n) {
							g << "Ciclu negativ!";
							return;
						}
                        else
                        {
                            coada.push(nod);
                            marcheaza[nod]=1;
                            frecventa[nod]++;
                        }
                    }
                }
            }
			coada.pop();
            marcheaza[x]=0;
  
        }
       
        {
            for(int i=2;i<=n;i++)
                g<<distanta[i]<<" ";
        }
    }
     
};
int main()
{
    graf X("bellmanford.in","bellmanford.out");
    X.bellmanford();
    return 0;
}