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

using namespace std;

const int NMAX = 5e4+9;

const int INF = 1e9+9;

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

#define pii pair<int,int>

int f[NMAX],cost[NMAX];

int n,i,j,m;

vector<pii>g[NMAX];

queue<int>q;

void bf (int startnode = 1);

int main()
{
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        int a,b,cost;
        fin>>a>>b>>cost;
        g[a].push_back ({b,cost});
    }
    bf();
    return 0;
}

void bf (int startnode)
{
    for (i=1; i<=n; i++)
    {
        cost[i]=INF;
    }
    cost[startnode]=0;
    q.push (startnode);
    while (!q.empty ())
    {
        int node=q.front();
        q.pop();
        for (auto it : g[node])
        {
            if (cost[it.first]>cost[node]+it.second)
            {
                cost[it.first]=cost[node]+it.second;
                q.push (it.first);
                f[it.first]++;
                if (f[it.first]>n)
                {
                    fout<<"Ciclu negativ!";
                    return ;
                }
            }
        }
    }
    for (i=2; i<=n; i++)
    {
        fout<<cost[i]<<' ';
    }
}