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

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

int N, M, Nr[50001];
int x, y, z;
queue <int> Q;
bool Vis[50001];
long long D[50001];

float BinarySearch();
bool BellmanFord(int x);
void Refresh();

vector <pair<int,int> > G[50001];

int main()
{
    is >> N >> M;
    for ( int i = 1; i <= M; ++i )
    {
        is >> x >> y >> z;
        G[x].push_back(make_pair(y,z));
    }

    if ( BellmanFord(0) == 0 )
        os << "Ciclu negativ!";
    else
    {
        for ( int i = 2; i <= N; ++i )
            os << D[i] << " ";
    }

    is.close();
    os.close();
}

float BinarySearch()
{
    int lo(100), hi(100000*100+1), mid;
    while ( lo < hi )
    {
        mid = (lo + hi)/2;
        if ( BellmanFord(mid) == 0 )
            hi = mid;
        else
            lo = mid+1;
    }
    return hi/100;
}

bool BellmanFord(int x)
{
    Refresh();
    int node;

    while ( !Q.empty() )
    {
        node = Q.front();
        Q.pop();
        Vis[node] = 0;
        for ( const auto& v : G[node] )
        {
            if ( D[v.first] > D[node] + (v.second-x) && Vis[v.first] == false )
            {
                if ( Nr[v.first] > N )
                    return 0;
                D[v.first] = D[node] + (v.second-x);
                Vis[v.first] = 1;
                Q.push(v.first);
                Nr[v.first]++;
            }
            if ( D[v.first] > D[node] + (v.second-x) && Vis[v.first] == true )
                D[v.first] = D[node] + v.second-x;
        }
    }
    return 1;
}

void Refresh()
{
    while ( !Q.empty() )
        Q.pop();
    Q.push(1);
    Nr[1] = 1;
    D[1] = 0;
    Vis[1] = 1;
    for ( int i = 2; i <= N; ++i )
    {
        D[i] = 0x3f3f3f3f;
        Vis[i] = 0;
        Nr[i] = 0;
    }

}