#include<bits/stdc++.h>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,i,j,a,b,c,x;
vector<pair<int,int>>graf[1001];
bool incoada[1001];
int nrmuchii[1001];
int dist[1001];
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        graf[a].push_back({b,c});
    }
    for(i=1;i<=n;i++)
    {
         incoada[i]=false;
         dist[i]=1e9;
    }

    int sursa=1;
    dist[sursa]=0;
    nrmuchii[sursa]=1;
    incoada[sursa]=true;
    queue<int>q;
    q.push(sursa);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
       incoada[x]=false;

       if(nrmuchii[x]>n)
       {
            g<<"Ciclu negativ!";
            exit(0);
       }
       for(auto it:graf[x])
       {
           if(dist[it.first]>dist[x]+it.second)
           {
               dist[it.first]=dist[x]+it.second;
               nrmuchii[it.first]=nrmuchii[x]+1;
               if(!incoada[it.first])
               {
                   q.push(it.first);
                   incoada[it.first]=true;
               }
           }
       }
    }
    for(i=2;i<=n;i++)
        g<<dist[i]<<" ";
    f.close();
    g.close();
    return 0;
}