#include <fstream>
#include <vector>
#include <queue>
#define pb push_back
#define mp make_pair
#define INF 0x3f3f3f
#include <cstring>
using namespace std;

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

vector < pair < int, int > > G[1001];
vector < pair < int, int > > :: iterator it;
queue <int> q;
bool sel[1001];
int n,m,x,y,c,D[1001],nod,ItNod[1001],i;

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

memset(sel, false, sizeof(sel));
memset( D, INF, sizeof(D) );
D[1] = 0;
memset( ItNod, 0, sizeof(ItNod) );
q.push(1);sel[1]=true;
while (!q.empty())
{
  nod=q.front();
  sel[nod]=false;

  for (it=G[nod].begin();it!=G[nod].end();it++)
     if (D[(*it).first]>D[nod]+(*it).second)
       {
           D[(*it).first]=D[nod]+(*it).second;
           if (!sel[(*it).first])
           {
               q.push((*it).first);
               sel[(*it).first]=true;
               if(++ItNod[(*it).first]>n)
                    {
                        g<<"Ciclu negativ!\n";
                        return 0;
                    }
           }
       }
    q.pop();
}
for (i=2;i<=n;i++) g<<D[i]<<' ';
return 0;
}