#include<fstream>
#include<vector>
#include<queue>
#define INF 1<<30
using namespace std;
int m,n,nr[50001],dist[50001];
vector<pair<int,int> >v[50001];
queue<int> q;
bool viz[50001];
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");


void Citire()
{
    int x,y,c;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
}

void Initializare()
{
    for(int i=2;i<=n;i++)
    {
        dist[i]=INF;
    }
}

void BellmanFord()
{
    int k,c,d;
    q.push(1);
    viz[1]=1;
    while(!q.empty())
    {
        k=q.front();
        for(int i=0;i<v[k].size();i++)
        {
            d=v[k][i].first,c=v[k][i].second;
            if(dist[d]>dist[k]+c)
            {
                dist[d]=dist[k]+c;
                if(viz[d]==0)
                {
                    q.push(d);
                    viz[d]=1;
                }
                nr[d]++;
                if(nr[d]>n-1)
                {
                    fout<<"Ciclu negativ!";
                    return;
                }
            }
        }
        q.pop();
        viz[k]=0;
    }
    for(int i=2;i<=n;i++)
    {
        fout<<dist[i]<<" ";
    }
}

int main()
{
    Citire();
    Initializare();
    BellmanFord();
    return 0;
}