#include <fstream>
#include <vector>
#include <deque>
#include <bitset>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,nod,cost,a,b,c,d[50010],cnt[50010];
vector <pair<int,int>> v[50010];
deque <int> Q;
bitset<50010> q;
int main()
{
    f>>n>>m;
    for(;m;m--)
    {
        f>>a>>b>>c;
        v[a].push_back(make_pair(c,b));
    }
    for(int i=2;i<=n;i++)
        d[i]=500000000;
    Q.push_back(1);q[1]=1;
    while(Q.size())
    {
        nod=Q.front();
        Q.pop_front();
        q[nod]=0;
        for(auto it:v[nod])
            if(d[nod]+it.first<d[it.second])
            {
                d[it.second]=d[nod]+it.first;
                if(!q[it.second])
                {
                    cnt[it.second]++;
                    if(cnt[it.second]>n)
                    {
                        g<<"Ciclu negativ!";
                        return 0;
                    }
                    q[it.second]=1;
                    Q.push_back(it.second);
                }
            }
    }
    for(int i=2;i<=n;i++)
        if(d[i]<500000000)
            g<<d[i]<<' ';
        else g<<"0 ";
    return 0;
}