#include<cstdio>
#include<vector>
#include<deque>
using namespace std;
const int vmax=50000005;
const int nmax=50000;
deque<int> dq;
struct sp
{
    int y,z;
};
vector<sp> ve[nmax+5];
int co[nmax+5];
bool inq[nmax+5];
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int n,m,i,j,x,y,z,nr=0;
    sp tm;
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        tm.y=y;
        tm.z=z;
        ve[x].push_back(tm);
    }
    for(i=1; i<=n; i++)
        co[i]=vmax;
    co[1]=0;
    dq.push_back(1);
    while(!dq.empty() && nr/m<=n)
    {
    x=dq.front();
    inq[x]=0;
    dq.pop_front();
    for(i=ve[x].size()-1;i>=0;i--)
    if(co[ve[x][i].y]>co[x]+ve[x][i].z)
    {
       co[ve[x][i].y]=co[x]+ve[x][i].z;
       if(inq[ve[x][i].y]==0)
       {
           inq[ve[x][i].y]=1;
           nr++;
           dq.push_back(ve[x][i].y);
       }
    }
    }
    if(nr/m<=n)
    {
    for(i=2;i<=n;i++)
    printf("%d ",co[i]);
    }
    else
    printf("Ciclu negativ!");
    printf("\n");
    return 0;
}