#include <fstream>
#include <queue>
#include <utility>
#include <vector>
#define infinity 1000000000
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

long long a[10000][10000];
int n,m,x,y,c,nd[50001];
bool e_in_q[10000];
int verif[10000];

vector<pair<int,int>> G[100000];

queue<int> q;
bool ok=1;
void Ford(int nod)
{
    q.push(1);
    for(auto x:G[1])
        q.push(x.first);
    for(int i=1;i<=n;i++)
    {
        if(a[1][i]!=0&&a[1][i]!=infinity)
        {
            q.push(i);
            nd[i]=a[1][i];
        }
    }
    q.pop();
    while(!q.empty())
    {

        int nod_curent=q.front();
        q.pop();
        verif[nod_curent]++;
        if(verif[nod_curent]>=n)
        {
            cout<<"Ciclu negativ!";
            ok=0;
            return;
        }
        for(int i=1;i<=n;i++)
        {
            if(a[nod_curent][i]+nd[nod_curent]<nd[i]&&e_in_q[nod_curent]==0)
            {
                q.push(i);
                e_in_q[i]=1;
                nd[i]=a[nod_curent][i]+nd[nod_curent];
            }
        }
        e_in_q[nod_curent]=0;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
    for(int i=2;i<=n;i++)
        nd[i]=infinity;
    Ford(1);
    if(ok==0) return 0;
    for(int i=2;i<=n;i++)
        cout<<nd[i]<<" ";
}