import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
 
class BellManFord {

    private final int INF = 1 << 27;
    private Integer dist[];
    private int parrtent[];
    private boolean negativCycle;

    public BellManFord(ArrayList<Edge> adj[], int source) {
        this.dist = new Integer[adj.length];
        this.parrtent = new int[adj.length ];
        this.negativCycle = false;
        this.shortestPath(adj, source);

    }

    private void shortestPath(ArrayList<Edge> graph[], int source) {
        int numberVertex = graph.length - 1;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] inQueue = new boolean[graph.length];
        int[] visted = new int[graph.length];
        for(int i = 1; i < dist.length; i++){
            if(i == source){
                dist[i] = 0;
            }else {
                dist[i] = INF;
            }
            visted[i] = 0;
            inQueue[i] = false;
        }

        queue.add(source);
        inQueue[source] = true;
        while (!queue.isEmpty()){
            int current = queue.poll();
            inQueue[current] = false;

            for(Edge neighbor : graph[current]){
                if( dist[neighbor.getNode()] > dist[current] + neighbor.getCost()){
                    dist[neighbor.getNode()] = dist[current] + neighbor.getCost();
                    parrtent[neighbor.getNode()] = current;
                    if(inQueue[neighbor.getNode()] == false){
                        inQueue[neighbor.getNode()] = true;

                        if(visted[neighbor.getNode()] > numberVertex){
                            negativCycle = true;
                            break;
                        }else {
                            queue.add(neighbor.getNode());
                            visted[neighbor.getNode()]++;
                        }
                    }
                }
            }

            if (negativCycle == true)
                break;
        }
    }

    public boolean isNegativCycle() {
        return negativCycle;
    }

    public Integer[] getMinDist(){
        return dist;
    }
}

 
class Edge {
    private int node;
    private int cost;
 
    public Edge(){
        this(0, 0);
    }
 
    public Edge(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }
 
    public int getNode() {
        return node;
    }
 
    public void setNode(int node) {
        this.node = node;
    }
 
    public int getCost() {
        return cost;
    }
 
    public void setCost(int cost) {
        this.cost = cost;
    }
}
 
public class Main {
    private static final String INPUT = "bellmanford.in";
    private static final String OUTPUT = "bellmanford.out";

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new FileReader(INPUT), 80960);
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(OUTPUT), 80960);
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine().trim());
        int numberVertex, numberEdge, source;
        numberVertex = Integer.parseInt(stringTokenizer.nextToken());
        numberEdge = Integer.parseInt(stringTokenizer.nextToken());
        source = 1;

        ArrayList<Edge>[] graph = (ArrayList<Edge>[]) new ArrayList[numberVertex + 1];
        for(int i = 0; i <= numberVertex; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i = 1; i <= numberEdge; i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine().trim());
            int u = Integer.parseInt(stringTokenizer.nextToken());
            int v = Integer.parseInt(stringTokenizer.nextToken());
            int cost = Integer.parseInt(stringTokenizer.nextToken());

            graph[u].add(new Edge(v, cost));
        }
        BellManFord algoritm = new BellManFord(graph, source);

        if(algoritm.isNegativCycle()){
            bufferedWriter.write("Ciclu negativ!");
            bufferedWriter.newLine();
        }else{
            String rez = "";
            for(int i = 2; i <= numberVertex; i++){
                rez = rez + algoritm.getMinDist()[i] + " ";
                //bufferedWriter.write(algoritm.getMinDist()[i] + " ");
            }
	    bufferedWriter.write(rez);
            bufferedWriter.newLine();
        }

        bufferedReader.close();
        bufferedWriter.close();
    }
}