#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector <int> v[50010],c[50010];
queue <int> q;
bool in[50010];
int nre[50010],d[50010];
int n,m,i,j;

int main()
{
    fin >> n >> m;
    for (i=1; i<=m; i++)
    {
        int A,B,C;
        fin >> A >> B >> C;
        v[A].push_back(B);
        c[A].push_back(C);
        if (A==1)
            d[B]=C;
    }
    q.push(1);
    in[1]=1;
    nre[1]=1;
    for (i=2; i<=n; i++)
//        if (d[i]==0)
            d[i]=250000100;
    d[1]=0;
    while (!q.empty())
    {
        int nod=q.front();
        q.pop();
        in[nod]=0;
        for (i=0; i<v[nod].size(); i++)
        {
            int vecin=v[nod][i];
            int cost=c[nod][i];
            if (d[vecin]>d[nod]+cost)
            {
                d[vecin]=d[nod]+cost;
                if (in[vecin]==0)
                {
                    in[vecin]=1;
                    q.push(vecin);
                    nre[vecin]++;
                    if (nre[vecin]>=n)
                        {
                            fout << "Ciclu negativ!\0";
                            return 0;
                        }
                }
            }
        }
    }
    for (i=2; i<=n; i++)
        fout << d[i] << ' ';
    fout << '\n';
}