package com.company;

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
import java.io.FileWriter;
public class Main {
    static class Edge {
        int x;
        int y;
        int c;
    }
    static Edge[] edges= new Edge[250010];
    static int[] distance= new int[50005];

    static boolean bellman (int N, int M)
    {
        for(int i=1; i<=N; i++)
        {
            distance[i]=50000000;
        }
        distance[1]=0;
        for(int i=1; i< N; i++)
            for(int j=1; j<=M; j++) {
                int u = edges[j].x;
                int v = edges[j].y;
                int w = edges[j].c;

                if (distance[u] + w < distance[v])
                    distance[v] = distance[u] + w;
            }
        for(int j=1; j<=M; j++)
        {
            int u = edges[j].x;
            int v = edges[j].y;
            int w = edges[j].c;
            if (distance[u] + w < distance[v])
                return false;
        }
        return true;
    }



    public static void main(String[] args) {
        int N=0;
        int M=0;
        try{
            File myfile= new File("bellmanford.in");

            Scanner myReader= new Scanner(myfile);
            N= myReader.nextInt();
            M= myReader.nextInt();
            for (int i=1; i<=M; i++) {
                edges[i] = new Edge();
                edges[i].x = myReader.nextInt();
                edges[i].y = myReader.nextInt();
                edges[i].c = myReader.nextInt();
            }
        } catch (IOException e) {}

        boolean val=bellman(N,M);
        try {
            FileWriter myWriter = new FileWriter("bellmanford.out");
            if( val== false)
                myWriter.write("Ciclu negativ!");
            else
                for (int i=2; i<=N; i++)
                {
                    Integer d=  distance[i];
                    myWriter.write(d.toString()+" ");

                }
                myWriter.close();
        } catch (IOException e) {}

    }
}