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