#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

#define INF 0x3f3f3f3f
#define pb push_back
#define mp make_pair

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

vector < pair < int, int > > G[50001];
queue <int> Q;
int n,m,x,y,c,i;
int C[50001],Nr[50001];
bool Sel[50001],ok=true;

void Expand (int nod)
{

    for (int i=0; i<G[nod].size(); i++)
       if (C[nod]+G[nod][i].second < C[G[nod][i].first])
       {
          C[G[nod][i].first]=C[nod]+G[nod][i].second;
          if (!Sel[G[nod][i].first])
             Q.push(G[nod][i].first),
             Sel[G[nod][i].first]=true;
             if (++Nr[G[nod][i].first] > n)
             {
                 g<<"Ciclu negativ!\n";
                 ok=false;
             }
       }
}

void BellmanFord ()
{
    int nod;

    memset (C, INF, sizeof(C));
    memset (Sel, false, sizeof(Sel));
    memset (Nr , 0, sizeof(Nr));
    Q.push(1), Sel[1]=true, C[1]=0;

    while (!Q.empty() && ok)
    {
        nod=Q.front();
        Expand(nod);
        Sel[nod]=false;
        Q.pop();
    }
}

int main ()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        G[x].pb(mp(y,c));
    }

BellmanFord();

if (ok) for (i=2;i<=n;i++) if (C[i]!=INF) g<<C[i]<<' '; else g<<"0 ";

return 0;
}