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

using namespace std;
	
ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");

const int INF = 0x3f3f3f3f;

int n,m;
vector <int> v[50001];
vector < pair <int,int> > p[50001];
queue <int> q;
bitset <50001> ok;
int cnt[50001];
vector <int> dist(50001,INF);

int main()
{
    int a,b,k;
    bool negative_cycle=0;
    in>>n>>m;
    for (int i=1;i<=m;i++)
    {
        in>>a>>b>>k;
        v[a].push_back(b);
        p[a].push_back({b,k});
    }
    q.push(1),dist[1]=0,ok[1]=1;
    while (!q.empty()&&!negative_cycle)
    {
        int x=q.front();
        q.pop();
        ok[x]=0;
        for (int i=0;i<p[x].size();i++)
            if (dist[x]<INF)
                if (dist[p[x][i].first]>dist[x]+p[x][i].second)
                {
                    dist[p[x][i].first]=dist[x]+p[x][i].second;
                    if (!ok[p[x][i].first])
                    {
                        if (cnt[p[x][i].first]>n)
                            negative_cycle=1;
                        else 
                        {
                            q.push(p[x][i].first);
                            cnt[p[x][i].first]++;
                            ok[p[x][i].first]=1;
                        }
                    }
                }
    }
    if (negative_cycle)
        out<<"Ciclu negativ!";
    else 
        for (int i=2;i<=n;i++)
            out<<dist[i]<<" ";
    return 0;
}