#include <iostream>
#include <fstream>
#include <list>
#include <stack>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m;
list <int> adj[50100];
list <int> cost[50100];
int dist[50100];
int frecv[50100];
bool incoada[50100];
int c[10000000];

void bell(int source)
{
    for(int i=1;i<=n;++i)
        dist[i]=1<<30;
    dist[source]=0;
    c[1]=source;
    incoada[source]=1;
    int inc,sf;
    inc=sf=1;
    while(inc<=sf)
    {
        int nc=c[inc];
        incoada[nc]=0;
        if(frecv[nc]>=n)
        {
            g<<"Ciclu negativ!";
            return ;
        }
        list <int> :: iterator i,j;
        for(i=adj[nc].begin(),j=cost[nc].begin();i!=adj[nc].end();++i,++j)
        {
            int u=*i;
            int cat=*j;
            if(dist[u]>dist[nc]+cat)
            {
                dist[u]=dist[nc]+cat;
                frecv[u]++;
                if(!incoada[u])
                {
                    c[++sf]=u;
                    incoada[u]=1;
                }
            }

        }
        ++inc;
    }
    for(int i=2;i<=n;++i)
        g<<dist[i]<<' ';
}

int main()
{f>>n>>m;
for(int i=1;i<=m;++i)
{
    int a,b,c;
    f>>a>>b>>c;
    adj[a].push_back(b);
    cost[a].push_back(c);
}
bell(1);

        return 0;
}