#include <fstream>
#include <vector>
#define Nmax 500001
#define Mmax 250001
using namespace std;

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

int n, m;
vector<pair<int, int>> mat[Nmax];
vector<int> dist(Nmax, 1e9);
int viz[Nmax];


void dfs(int x)
{
    for(auto it : mat[x])
    {
         if(viz[it.first] == 0)
         {
             viz[it.first] = 1;
            if(dist[x] + it.second < dist[it.first])
            {
                cout << "Ciclu negativ";
                exit(0);
            }

            else
                dfs(it.first);
         }
    }
}

int main()
{
    cin >> n >> m;

    for(int i = 0, a, b, c; i<m; i++)
    {
        cin >> a >> b >> c;
        mat[a].push_back({b, c});
    }

    dist[1] = 0;

    for(int i = 1; i<=n; i++)
        for(auto it : mat[i])
        {
            if(dist[i] + it.second < dist[it.first])
                dist[it.first] = dist[i] + it.second;
        }

        viz[1] = 1;
    dfs(1);

    for(int i = 2; i<=n; i++)
        cout << dist[i] << ' ';
}