#include<cstdio>
#include<queue>
#define Nmx 50001
#define INF 2000001

using namespace std;

int n,m,dist[Nmx],viz[Nmx];
struct nod
{
	int inf,cost;
	nod *urm;
};
nod *G[Nmx];
queue<int>Q;

void add(int x,int y,int c)
{
	nod *aux=new nod;
	aux->inf = y;
	aux->cost = c;
	aux->urm = G[x];
	G[x] = aux;
}

void citire()
{
	int x,y,c;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&c);
		add(x,y,c);
	}
}

void afisare()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x,y,c;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        if(dist[x]+c<dist[y])
        {
            printf("Ciclu negativ!\n");
            return ;
        }
    }
    for(int i=2;i<=n;++i)
        if(dist[i]==INF)
            printf("0 ");
        else printf("%d ",dist[i]);
    printf("\n");
}

void solve()
{
	for(int i=2;i<=n;++i)
		dist[i]=INF;
	Q.push(1);
	viz[1]=1;
	long long pas=0;
	while(!Q.empty()&&pas<=(long long)n*m)
	{
	    ++pas;
		int x = Q.front();
		viz[x]=0;
		Q.pop();
		for(nod *p=G[x];p;p=p->urm)
			if(p->cost+dist[x]<dist[p->inf])
			{
				dist[p->inf]=p->cost+dist[x];
				if(viz[p->inf]==0)
				{
					Q.push(p->inf);
					viz[p->inf]=1;
				}
			}
	}
	afisare();
}

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	citire();
	solve();
	return 0;
}