#include <fstream>
#include <vector>
using namespace std;
 
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
 
#pragma region Global Variables
 
const int maxn = 50005;
 
int num_vertices, num_edges;
vector< pair<int,int> > graph[maxn];
vector<int> to_visit, is_visited, dist;
 
#pragma endregion
 
#pragma region Read&Write
 
void Read()
{
    int a,b,c,i;
 
    f>>num_vertices>>num_edges;
 
    for(i=1;i<=num_edges;i++)
    {
        f>>a>>b>>c;
        graph[a].push_back(make_pair(b,c));
    }
}
 
void Write(int negative_cycle)
{
    if(negative_cycle)
        g<<"Ciclu negativ!";
    else
    {
        for(int i=2; i<=num_vertices; i++)
            g<<dist[i]<<' ';
        g<<'\n';
    }
}
 
#pragma endregion
 
int main()
{
    //Local variables
    int ok = 1, visited = 0, i, j, tovisit, vecin;
    vector<int>::iterator it;
 
    //Read the graph
    Read();
 
    //Resize vectors and assign memory
    is_visited.resize(num_vertices+1), dist.resize(num_vertices+1);
    is_visited.assign(num_vertices+1, 0), dist.assign(num_vertices+1, 5004);
 
    //Start Solving
    to_visit.push_back(1);
    is_visited[1] = 1;
    dist[1] = 0;
    while(visited <= num_vertices && ok)
    {
        ok = 0;
        for(i = 0; i < to_visit.size(); i++)
        {
            tovisit = to_visit[i];
            for(j = 0; j<graph[tovisit].size(); j++)
            {
                vecin = graph[tovisit][j].first;
                if(dist[vecin] > dist[tovisit] + graph[tovisit][j].second) 
                {
                    dist[vecin] = dist[tovisit] + graph[tovisit][j].second;
 
                    if(!is_visited[vecin])
                        to_visit.push_back(vecin), is_visited[vecin] = 1;
 
                    ok = 1;
                }
            }
        }
 
        visited++;
    }
 
    //Write correct solution
    Write(ok);
 
    return 0;
}