#include<fstream>
#include<vector>
#include<queue>
#define N 50010
using namespace std;

int n,m,vmin[N],veer;
vector<pair<int,int> > g[N];

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

void bellmanford() {
    vector<pair<int,int> >::iterator it;
    queue<int> q;

    q.push(1); vmin[1]=0;

    while(!q.empty()) {

        for(it=g[q.front()].begin();it!=g[q.front()].end();++it) if(vmin[it->first]>vmin[q.front()] + it->second) {

            vmin[it->first]=vmin[q.front()] + it->second;
			
			if(vmin[it->first]<-40000) {
				out << "Ciclu negativ!";
				veer=1;
				return;
			}

            q.push(it->first);

        }

        q.pop();
    }

}

int main() {
    int i,a,b,c;

    in >> n >> m;

    for(i=1;i<=m;++i) {

        in >> a >> b >> c;

        g[a].push_back(pair<int,int>(b,c));
    }

    for(i=1;i<=n;++i)
        vmin[i]=1<<20;

    bellmanford();
	
	if(veer==0)
		for(i=2;i<=n;++i)
			out << vmin[i] << " ";

    return 0;
}