#include <cstdio>
#include <queue>
using namespace std;

const int inf=1<<30;
int n,d[50001],inlista[50001],nrintrariinlista[50001];
queue <int> c;
struct nod
{
    int x,c;
    nod* u;
}*v[50001];

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int m,x;
    nod *v1;
    scanf("%d%d",&n,&m);
    while(m)
    {
        --m;
        v1=new nod;
        scanf("%d",&x);
        v1->u=v[x];
        v[x]=v1;
        scanf("%d",&x);
        v1->x=x;
        scanf("%d",&x);
        v1->c=x;
    }
    for(x=2;x<=n;++x) d[x]=inf;
    c.push(1);
    ++nrintrariinlista[1];
    ++inlista[1];
    while(!c.empty())
    {
        x=c.front();
        v1=v[x];
        while(v1)
        {
            if(d[v1->x]>d[x]+v1->c)
            {
                d[v1->x]=d[x]+v1->c;
                if(!inlista[v1->x])
                {
                    inlista[v1->x]=1;
                    ++nrintrariinlista[v1->x];
                    if(nrintrariinlista[v1->x]==n)
                    {
                        printf("Ciclu negativ!\n");
                        return 0;
                    }
                    c.push(v1->x);
                }
            }
            v1=v1->u;
        }
        inlista[x]=0;
        c.pop();
    }
    for(x=2;x<=n;++x) printf("%d ",d[x]);
    printf("\n");
    return 0;
}