#include <bits/stdc++.h>
using namespace std;
ifstream fin("rege1.in");
ofstream fout("rege1.out");
struct muchie{
int x,c;
};
constexpr int N = 50005;
int n,m;
vector<muchie> g[N];
int dist[N], viz[N],nrViz[N];
queue<int> q;
int main(){
fin>>n>>m;
for(int i=1; i<=m; ++i){
int x,y,c;
fin>>x>>y>>c;
g[x].push_back({y,c});
}
for(int i=2; i<=n; ++i)
dist[i]=INT_MAX;
q.push(1);
viz[1]=1;
nrViz[1]=1;
while(!q.empty()){
int nod = q.front();
viz[nod]=0;
q.pop();
for(muchie e : g[nod]){
int vecin = e.x;
int cost = e.c;
nrViz[vecin]=nrViz[nod]+1;
if(dist[vecin]>dist[nod]+cost){
dist[vecin]=dist[nod]+cost;
if(nrViz[vecin]>=n){
fout<<"Ciclu negativ!";
return 0;
}
nrViz[vecin]=nrViz[nod]+1;
if(viz[vecin]==0){
q.push(vecin);
viz[vecin]=1;
}
}
}
}
for(int i=2; i<=n; ++i)
fout<<dist[i]<<" ";
return 0;
}