#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;

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

const int NMAX = 5e4 + 1;
const int INF = 1e9;

vector<int> dp(NMAX,INF),cate(NMAX);
vector<pair<int,int>> vecini[NMAX];

bitset<NMAX> inq;

int main()
{
    int n,a,b,c,m; cin >> n >> m;
    for(int i = 1; i <= m ; i++)
        {
            cin >> a >> b >> c;
            vecini[a].push_back({b,c});
        }

    ///Bellman - Ford
    dp[1] = 0;
    queue<int> q; q.push(1);


    inq[1] = 1;

    while(!q.empty())
        {
            int v = q.front(); q.pop();
            inq[v] = 0;

            for(auto it : vecini[v])
                {
                    if((dp[v] + it.second) < dp[it.first])
                        {
                            dp[it.first] = dp[v] + it.second;
                            if(!inq[it.first])
                                {
                                    q.push(it.first);
                                    inq[it.first] = 1;
                                    cate[it.first]++;
                                    if(cate[it.first] > n)
                                        {
                                            cout << "Ciclu negativ!";
                                            return 0;
                                        }
                                }
                        }
                }
        }

    for(int i = 2; i <= n ; i++) cout << dp[i] << " ";

}