#include<stdio.h>
#include<vector>
#include<queue>
#define MAX 50005
const int inf=1<<30;
using namespace std;

vector<int> G[MAX],C[MAX];
queue<int> Q;

int n,m,dmin[MAX],cost[MAX];

int main(){
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
int i;
scanf("%d %d",&n,&m);

for(i=1;i<=m;i++){
int temp1,temp2,temp3;

scanf("%d %d %d",&temp1,&temp2,&temp3);
G[temp1].push_back(temp2);
C[temp1].push_back(temp3);
}

Q.push(1);
for(i=2;i<=n;i++)dmin[i]=inf;
dmin[1]=0;


while(!Q.empty()){
int x=Q.front();

Q.pop();
	for(i=0;i<G[x].size();i++){
	int y=G[x][i],z=C[x][i];;
	if(dmin[x]+z<dmin[y]){dmin[y]=dmin[x]+z;Q.push(y);cost[y]++;if(cost[y]>n-1){printf("Ciclu negativ!");return 0;}}
	}

}


for(i=2;i<=n;i++){
if(dmin[i]==inf)dmin[i]=0;
printf("%d ",dmin[i]);
}

return 0;
}