#include <fstream>
#include <vector>
#include <queue>
using namespace std;
struct arc
    {
    int vf;
    int cost;
    };
vector <arc> v[50001];
bool inqueue[50001],ok;
int nr[50001],vf;
long long int d[50001];
queue <int> q;
int main()
{
    ifstream fin ("bellmanford.in");
    ofstream fout ("bellmanford.out");
    int n,m,x,y,c,l;
    fin>>n>>m;
    for (int i=2;i<=n;i++)
        d[i]=50000000;
    for (int i=1;i<=m;i++)
        {
        fin>>x>>y>>c;
        v[x].push_back({y,c});
        }
    q.push(1);
    inqueue[1]=1;
    nr[1]=1;
    ok=1;
    while (!q.empty()&&ok)
        {
        vf=q.front();
        q.pop();
        inqueue[vf]=0;
        l=v[vf].size();
        for (int i=0;i<l;i++)
            {
            x=v[vf][i].vf;
            c=v[vf][i].cost;
            if (d[vf]+c<d[x])
                {
                d[x]=d[vf]+c;
                if (!inqueue[x])
                    {
                    q.push(x);
                    inqueue[x]=1;
                    nr[x]++;
                    if (nr[x]==n)
                        ok=0;
                    }
                }
            }
        }
    if (ok==0)
        fout<<"Ciclu negativ!";
    else
        for (int i=2;i<=n;i++)
            fout<<d[i]<<" ";
    fin.close();
    fout.close();
    return 0;
}