#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <ctime>
#include <utility>

using namespace std;

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

const int MAXN = 50005;

vector<pair<int,int> > G[MAXN];
vector<int> d(MAXN, ((1<<31)-1));
int n, m;
queue <int> Q;
bitset < MAXN > in_Q;
int in_Q_s[MAXN];

inline void bellmanford()
{
    for(Q.push(1), d[1] = 0, in_Q[1] = true ; !Q.empty(); Q.pop() )
    {
        int node = Q.front();
        in_Q[node] = false;
        for(vector< pair<int, int > > :: iterator it = G[node].begin(); it != G[node].end(); ++ it)
        {
            int newnode = it->first;
            int cost = it->second;
            if(d[newnode] > d[node] + cost)
            {
                d[newnode] = d[node] + cost;
                if(!in_Q[newnode])
                {
                    if(in_Q_s[newnode] > n)
                    {
                        cout << "Ciclu negativ!\n";
                        return;
                    }
                    ++ in_Q_s[newnode];
                    in_Q[newnode] = true;
                    Q.push(newnode);
                }
            }
        }
    }
    for(int i = 2; i <= n ; ++ i)
        cout << d[i] << " ";
}
int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= m ; ++ i)
    {
        int x, y, z;
        cin >> x >> y >> z;
        G[x].push_back(make_pair(y, z));
    }
    bellmanford();
    return 0;
}