#include <fstream>
#include <vector>

using namespace std;
ifstream fin  ("dijkstra.in");
ofstream fout ("dijkstra.out");

const long int NMAX = 50005;
const int INFINIT = 1 << 30;

struct edge {
    int x, y, z;
};

int N, M;
vector < edge > lista;
vector < int > dist(NMAX, INFINIT);

void bellmanford(int nod)
{
    bool negative_cycle = false;
    dist[nod] = 0;
    
    for(int i = 0; i < N - 1; i++)
        for(unsigned int j = 0; j < lista.size(); j++)
            if(dist[lista[j].y] > dist[lista[j].x] + lista[j].z)
                dist[lista[j].y] = dist[lista[j].x] + lista[j].z;
    
    for(unsigned int j = 0; j < lista.size() && !negative_cycle; j++)
        if(dist[lista[j].y] > dist[lista[j].x] + lista[j].z)
            negative_cycle = true;
    
    if(negative_cycle)
        fout << "Ciclu negativ!";
    else
        for(int i = 2; i <= N; i++)
            fout << dist[i] << ' ';
}

int main()
{
    fin >> N >> M;
    for(int i = 0 ; i < M; i++)
    {
        int x, y, z;
        fin >> x >> y >> z;
        edge e;
        e.x = x; e.y = y; e.z = z;
        lista.push_back(e);
    }

    bellmanford(1);
    fin.close();
    fout.close();
    return 0;
}