#include<fstream>
#include<bitset>
#include<vector>
#include<queue>
#define INF 0x3f3f3f
#define MAX 50010
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

queue < int > q;
vector< pair<int,int> > p[MAX];
int c[MAX],aparitie[MAX],N,M,a,b,cost,i,val;

void bellmanford()
        {
            q.push(1);
            while(!q.empty())
            {
                val=q.front();
                aparitie[val]++;
                q.pop();
                if(aparitie[val]>N)
                {
                    fout<<"Ciclu negativ!";
                    return;

                }
                for(int i=0;i<p[val].size();i++)
                {
                    if(c[p[val][i].first]>c[val]+p[val][i].second)
                    {
                       c[p[val][i].first]=c[val]+p[val][i].second;
                       q.push(p[val][i].first);
                    }
                }
            }
        }

int main()
{
            fin>>N>>M;
            for(i=1;i<=M;i++)
            {
                fin>>a>>b>>cost;
                p[a].push_back(make_pair(b,cost));
            }
            for(i=2;i<=N;i++)
                c[i]=INF;
            bellmanford();
            for(i=2;i<=N;i++)
                fout<<c[i]<<' ';
            return 0;
}