#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bellmanford.in"); ofstream g("bellmanford.out");
const int inf=1<<30; const int N=50006;
int n,m,dist[N],use[N];
struct vecin {int varf,cost;};
vector <vecin> L[N];
queue <int> Q;
int main()
{   int x,y,c,i;
    f>>n>>m;
    while(m--)
    {   f>>x>>y>>c;
        L[x].push_back((vecin){y,c});
    }
    // Bellman-Ford
    for(i=1; i<=n; i++) dist[i]=inf;
    Q.push(1); dist[1]=0;
    while(!Q.empty())
    {   x=Q.front(); Q.pop();
        use[x]++;
        if(use[x]==n) {g<<"Ciclu negativ!\n"; return 0;}
        vector <vecin> :: iterator it=L[x].begin(), sf=L[x].end();
        for(; it!=sf; ++it)
        {   if(dist[(*it).varf]>dist[x]+(*it).cost)
            {    dist[(*it).varf]=dist[x]+(*it).cost;
                Q.push((*it).varf);
            }
        }
    }
    for(i=2; i<=n; i++) g<<dist[i]<<" ";
    g<<"\n";  return 0;
}