#include <fstream>
#include<vector>
#include<queue>

using namespace std;

#define oo 1000000
#define MAX 50001

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

vector<pair<int, int>> A[MAX];
int d[MAX], vizitat[MAX], n, m, p;

typedef pair<int,int>pi;
priority_queue<pi, vector<pi>,greater<pi>>pq;

int main()
{
    in>>n>>m; p=1;
    int x, y, z;
    while(in>>x>>y>>z)
        A[x].push_back({y,z});

    for(int i=1;i<=n;i++)
        d[i]=oo;
    d[p]=0; vizitat[0]++;
    pq.push({0,p});
    while(!pq.empty())
    {
        int imin=pq.top().second;
        pq.pop();
        vizitat[imin]++;
        if(vizitat[imin]>n)
        {
            out<<"Ciclu negativ!"; return 0;
        }
        for(auto i: A[imin])
            if(d[i.first]>d[imin]+i.second)
            {
                d[i.first]=d[imin]+i.second;
                pq.push({d[i.first],i.first});
            }
        }

    for(int i=2;i<=n;i++)
        out<<d[i]<<' ';

    return 0;
}




//Dijkstra cu priority_quewe cu liste de adiacente
/*#include <fstream>
#include<vector>
#include<queue>

using namespace std;

#define oo 1000000
#define MAX 100000

ifstream in("dijkstra2.in");
ofstream out("dijkstra2.out");

vector<pair<int, int>> A[MAX];
int f[MAX], d[MAX]={3,2,1,0}, n, m, p;

struct compare{
    bool operator()(int a, int b)
    {
        return d[a]<d[b];
    }
};
priority_queue<int, vector<int>,compare>pq;

int main()
{
    pq.push(2);
    pq.push(1);
    pq.push(3);
    pq.push(0);
    while(!pq.empty())
    {
        out<<pq.top()<<' ';
        pq.pop();
    }
    return 0;
    in>>n>>m>>p;
    int x, y, z;
    while(in>>x>>y>>z)
    {
        A[x].push_back({y,z});
        A[y].push_back({x,z});
    }

    for(int i=1;i<=n;i++)
        d[i]=oo;
    d[p]=0;
    pq.push(p);
    while(!pq.empty())
    {
        int imin=pq.top();
        pq.pop();
        f[imin]=1;
        for(auto i: A[imin])
            if(!f[i.first] && d[i.first]>d[imin]+i.second)
            {
                d[i.first]=d[imin]+i.second;
                pq.push(i.first);
            }
        }

    for(int i=1;i<=n;i++)
        out<<(d[i]==oo?-1:d[i])<<' ';

    return 0;
}
*/