#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int DN=50005;
const int DM=250005;
int n,m,f,g,cost;
int dist[DN];
//int r[DN][DN];
pair<pair<int,int>,int>mc[DM];
vector<pair<int,int> >v[DN];
int bellman(int nod)
{
    for(int i=1;i<=n;i++)
        dist[i]=1e9;
    dist[nod]=0;
    int vf=0;
    for(int i=1;i<=n&&!vf;i++)
    {
        vf=1;
        for(int j=1;j<=m;j++)
        {
            f=mc[j].x.x;
            g=mc[j].x.y;
            cost=mc[j].y;
            if(dist[f]+cost<dist[g])
            {
                vf=0;
                dist[g]=dist[f]+cost;
            }
        }
        //cout<<i<<' '<<vf<<'\n';
    }
    return vf;
}
int main()
{
    cout<<"introduceti numarul de noduri ";
    fin>>n;
    cout<<"introduceti numarul de muchii ";
    fin>>m;
    for(int i=1;i<=m;i++)
        fin>>mc[i].x.x>>mc[i].x.y>>mc[i].y;
    if(!bellman(1))
    {
        fout<<"Ciclu negativ!";
        return 0;
    }
    for(int i=2;i<=n;i++)
        fout<<dist[i]<<' ';
}