#include <fstream>
#include <cstring>
#include <string>
#include <queue>
#define nmax 50001
#define inf 0x3f3f3f3f

using namespace std;

struct Graf {
    int nd;
    int cost;
    Graf *next;
};

void getData(Graf *G[nmax],int &n,int &m) {

    ifstream r("bellmanford.in");
    r>>n>>m;
    for (int k=1;k<=m;k++){
        int i,j,c;
        r>>i>>j>>c;
        Graf *p=new Graf;
        p->next=G[i];
        p->nd=j;
        p->cost=c;
        G[i]=p;
    }
    r.close();
}

void printDmin(int (&dmin)[nmax],int n) {

    ofstream w("bellmanford.out");
    for (int i=1;i<=n;i++)
        w<<dmin[i]<<" ";
    w.close();
}

void printError(string s) {

    ofstream w("bellmanford.out");
    w<<s<<endl;
    w.close();
}

void doBellmanFord(Graf *G[nmax], int n,int source) {
   int cnt[nmax],dmin[nmax];
   queue <int> Q;
   bool viz[nmax],ok=true;

   memset(cnt,0,sizeof(cnt));
   memset(dmin,inf,sizeof(dmin));
   memset(viz,false,sizeof(viz));

   Q.push(source);
   viz[source]=true;
   dmin[source]=0;
   while (!Q.empty() and ok) {
        int prec=Q.front();
        Q.pop();
        Graf *p=G[prec];
        viz[prec]=false;
        while (p and ok) {
            if (dmin[prec]+p->cost<dmin[p->nd]) {
                dmin[p->nd]=dmin[prec]+p->cost;
                if (!viz[p->nd]) {
                    Q.push(p->nd);
                    viz[p->nd]=true;
                    cnt[p->nd]++;
                }
            }
            if (cnt[p->nd]>n-1)
                ok=false;
            p=p->next;
        }
   }
   if (ok)
        printDmin(dmin,n);
   else
        printError("Ciclu negativ!");
}
int main () {
    int n,m;
    Graf *G[nmax];

    getData(G,n,m);
    doBellmanFord(G,n,1);
    return 0;
}