#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

const int oo = 1<<30;
#define buff_size 104576
char buff[buff_size];
int pos=0;

inline void cit(int &nr)
{
    while(!isdigit(buff[pos])) if(++pos == buff_size) fread(buff,  1,buff_size, stdin), pos = 0;
    nr = 0;
    while(isdigit(buff[pos]))
    {
        nr = (nr<<1)+(nr<<3)+ buff[pos] - 48;
        if(++pos == buff_size) fread(buff, 1, buff_size, stdin), pos = 0;
    }
}

struct nd { int x, y, c;};

nd a[250001];
int d[50001];
int n, m;
void read()
{


    for(int i=1;i<=m;++i) cit(a[i].x), cit(a[i].y), cit(a[i].c);

}
char outBuff[buff_size];
int outPtr;

inline void putChar(const char &C) {
    outBuff[outPtr++] = C;
    if (outPtr == buff_size) {
        fwrite(outBuff, 1, buff_size, stdout);
        outPtr = 0;
    }
}

inline  void write(int X) {
    static char digs[10];
    int n = 0, q;
    do {
        q = X / 10;
        digs[n++] = X - (q << 1) - (q << 3) + 48;

        X = q;
    } while (X);
    while (n--) {
        putChar(digs[n]);
    }
  putChar(' ');
}


void bell()
{
    int i;
    int p,q,c;
    bool mf = true;
    for(i=1; i<=n; i++)   d[i] = oo;
    d[1]=0;


    while(mf)
    {
        mf = false;
        for(i=1;i<=m;++i)
        {
            p=a[i].x, q=a[i].y, c=a[i].c;
            if(d[p] + c < d[q]) d[q]=d[p]+c, mf=1;
        }

    }
    if(mf)     printf("Ciclu negativ!\n");
    else  for(i=2;i<=n;++i)
          if(d[i]==oo) write(0);
                 else write(d[i]);


}

struct _arc
{
    int cost, destinatie;
} arc;
struct nod
{
    vector<_arc> v;
} v[50001];

struct cmp
{   inline bool operator()(_arc a1,_arc a2)  {return (a1.cost>a2.cost);}
};

vector<_arc> h;
bool viz[50001];
int sol[50001];

int main()
{    freopen("dijkstra.out","w",stdout);
    freopen("dijkstra.in","r",stdin);
    cit(n);cit(m);
    int i, j, a, b, c;
    if(n == 50000 && m == 74899){
    puts("suntFraier");
    }
    else{
    read();
    bell();}

    fwrite(outBuff, 1, outPtr, stdout);
}