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

#define vintp vector<pair<int,int> >::iterator

using namespace std;

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

int n,m,a,b,c,d[50001],p[50001],ap[50001],viz[50001];
vector <pair<int,int> > G[50001];
queue <int> Q;

bool bellman_ford ()
{
    for (int i=2; i<=n; ++i)
        d[i] = 100000000;

    Q.push (1);
    ap[1] = 1;
    viz[1] = 1;

    while (!Q.empty ())
    {
        int x = Q.front ();

        if (viz[p[x]])
        {
            viz[x] = 0;
            Q.pop ();
            continue;
        }

        for (vintp it = G[x].begin (); it != G[x].end(); ++it)
        {
            if (d[x] + it->second < d[it->first])
            {
                d[it->first] = d[x] + it->second;
                p[it->first] = x;

                ap[it->first] ++;

                if (ap[it->first] == n)
                    return 0;

                if (!viz[it->first])
                {
                    Q.push (it->first);
                    viz[it->first] = 1;
                }
            }
        }

        viz[x] = 0;
        Q.pop ();
    }
    return 1;
}

int main ()
{
    fin>>n>>m;

    for (int i=1; i<=m; ++i)
    {
        fin>>a>>b>>c;

        G[a].push_back (make_pair(b,c));
    }

    if (!bellman_ford ())
    {
        fout<<"Ciclu negativ!";
    }
    else
        for (int i=2; i<=n; ++i)
          fout<<d[i]<<" ";
}