#include <fstream>
#include <vector>
#include <deque>
#include <bitset>
#define DIM 50010
#define INF 2000000000
using namespace std;
int n,m,i,x,y,z,D[DIM],F[DIM],sol;
vector<pair<int,int> >L[DIM];
deque<int> c;
bitset<DIM> V;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
void BF(int a)
{
    c.push_back(a);
    V[a]=1;
    while(!c.empty())
    {
        int nod=c.front();
        c.pop_front();
        V[nod]=0;
        for(int i=0;i<L[nod].size();i++)
        {
            int vecin=L[nod][i].first;
            int cost=L[nod][i].second;
            if(D[vecin]>D[nod]+cost)
            {
                D[vecin]=D[nod]+cost;
                if(V[vecin]==0)
                {
                    F[vecin]++;
                    if(F[vecin]>=n)
                    {
                        fout<<"Ciclu negativ!";
                        sol=1;
                        return ;
                    }
                    c.push_back(vecin);
                    V[vecin]=1;
                }
            }
        }
    }
}
void IN(int *D, int x)
{
    for(int i=1;i<=n;i++)
        D[i]=INF;
    D[x]=0;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        L[x].push_back(make_pair(y,z));
    }
    IN(D,1);
    BF(1);
    if(sol==1)
        return 0;

    for(i=2;i<=n;i++)
        fout<<D[i]<<" ";

    return 0;
}