#include <fstream>
#include <vector>
#include <climits>
#include <queue>
using namespace std;
const int nmax=50005;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

vector <int> drum[nmax];
vector <int> cost[nmax];
queue <int> cod;

int timesinq[nmax]; // daca un nod a intrat in coada de mai mult de n ori , inseamna ca vom avea ciclu negativ
int mincost[nmax]; // costul minim din nodul 1 pana in nodul i
int n,m,i,x,y,z;
bool inq[nmax];

int bellmanford (int nodini)
{
    int nodac,nrvecini,costac,nodnou;
    inq[nodini]=1;
    mincost[nodini]=0;
    timesinq[nodini]++;
    cod.push(nodini);
    while (!cod.empty())
    {
        nodac=cod.front();
        cod.pop();
        inq[nodac]=0;
        costac=mincost[nodac];
        nrvecini=drum[nodac].size();
        for (i=0;i<nrvecini;i++)
        {
             nodnou=drum[nodac][i];
             if (costac+cost[nodac][i]<mincost[nodnou]) // verificam daca putem ajunge intr-un vecin cu un cost mai mic
             {
                 if (timesinq[nodnou]>n)
                  return 1; // ciclu negativ
                 if (inq[nodnou]==0) // vedem daca nu este in coada
                 {
                     inq[nodnou]=1;
                     cod.push(nodnou);
                 }
                 mincost[nodnou]=costac+cost[nodac][i]; // updatam cu costul mai mic
                 timesinq[nodnou]++;
             }
        }
    }
    return 0;
}

int main()
{
    f>>n>>m;
    for (i=1;i<=n;i++)
     mincost[i]=INT_MAX;
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        drum[x].push_back(y);
        cost[x].push_back(z);
    }
    if (bellmanford(1))
    {
        g<<"Ciclu negativ!";
        return 0;
    }

    for (i=2;i<=n;i++)
    {
        g<<mincost[i]<<" ";
    }

    return 0;
}