#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

struct vecin
{
    int vf, c;
};

vector<vecin> v[50001];
const int maxi=500000001;
int viz[50001],nr [50001], d[50001],m,n,cod;

queue<int> q;

void bellmanford(int nod){
    int p,u,x,i,y,c;
    viz[nod]=1;
    //p=u=1;
    //q[p]=nod;
    q.push(nod);
    while(!q.empty()){
        //x=q[p++];
        x = q.front();
        q.pop();
        viz[x] = 0;
        for (unsigned i = 0; i < v[x].size(); i++)
        {
            y = v[x][i].vf;
            c = v[x][i].c;
            if (d[x] + c < d[y])
            {
                d[y] = d[x] + c;
                if (!viz[y])
                {
                    //q[++u] = y;
                    q.push(y);
                    nr[y]++;
                    if (nr[y] == n)
                    {
                        g<< "Ciclu negativ!";
                        cod=1;
                        return;
                    }
                    viz[y] = 1;
                }
            }
        }
    }

}

int main()
{
    int x,y,c,i;
    vecin aux;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>c;
        aux.vf = y;
        aux.c = c;
        v[x].push_back(aux);
    }
    for(i=2;i<=n;i++)
            d[i]=maxi;
    bellmanford(1);
    if(cod==0)
        for(i=2;i<=n;i++)
            g<<d[i]<<" ";
    return 0;
}