#include <fstream>
#include <cstring>
#include <queue>

#define gL 50001
#define dL 50001
#define cntL 50001
#define useL 50001

using namespace std;

struct graf
{
    int nod,cost;
    graf *link;
}*g[gL];

int d[dL];
int N;

inline void add_edge_cost(int x,int y,int c)
{
    graf *p=new graf;
    p->nod=y;
    p->cost=c;
    p->link=g[x];
    g[x]=p;
}

inline int bellmanford(int nod)
{
    int cnt[cntL];
    int use[useL];
    queue <int> q;

    for(int i=1;i<=N;++i) d[i]=0x7fffffff;
    memset(cnt,0,sizeof(cnt));
    memset(use,0,sizeof(use));

    q.push(nod);
    d[nod]=0;

    for(;!q.empty();q.pop())
    {
        nod=q.front();
        use[nod]=0;

        for(graf *p=g[nod];p;p=p->link)
            if(d[p->nod]>d[nod]+p->cost)
            {
                d[p->nod]=d[nod]+p->cost;
                if(!use[p->nod])
                {
                    ++cnt[p->nod];

                    if(cnt[p->nod]>=N) return 1;

                    use[p->nod]=1;
                    q.push(p->nod);
                }
            }
    }

    return 0;
}

ifstream in;
ofstream out;

int main()
{
    int M,x,y,c;

    in.open("bellmanford.in");

    in>>N>>M;
    for(;M--;)
    {
        in>>x>>y>>c;
        add_edge_cost(x,y,c);
    }

    in.close();

    int cn=bellmanford(1);

    out.open("bellmanford.out");

    if(cn) out<<"Ciclu negativ!\n";
    else
    {
        for(int i=2;i<N;++i)
            out<<d[i]<<' ';
        out<<d[N]<<'\n';
    }

    out.close();

    return 0;
}