package infoarena.arhivaedu;

import static java.lang.System.err;
import java.io.*;
import java.util.*;

public class BellmanFord {
    Scanner in;
    PrintWriter out;

    class Edge {
        int target, weight;
        Edge(int target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }

    class Node {
        ArrayList<Edge> adj;
        int dist;
        Node parent;
        Node() {
            adj = new ArrayList<>();
            dist = Integer.MAX_VALUE;
            parent = null;
        }
    }

    int N, M;
    Node[] V;

    void solve() {
        N = in.nextInt();
        M = in.nextInt();
        V = new Node[N + 1];
        for (int i = 1; i <= N; i++) {
            V[i] = new Node();
        }
        for (int i = 1; i <= M; i++) {
            int x = in.nextInt(), y = in.nextInt(), c = in.nextInt();
            V[x].adj.add(new Edge(y, c));
        }
        if (!bellmanFord(1)) out.println("Ciclu negativ!");
        else {
            for (int i = 2; i <= N; i++) {
                out.print(V[i].dist + " ");
            }
            out.println();
        }
    }

    boolean bellmanFord(int source) {
        V[source].dist = 0;
        for (int k = 0; k < N - 1; k++) {
            for (int i = 1; i <= N; i++) {
                for (Edge e : V[i].adj) {
                    int newDist = V[i].dist + e.weight;
                    if (V[e.target].dist > newDist) {
                        V[e.target].dist = newDist;
                        V[e.target].parent = V[i];

                    }
                }
            }
        }
        for (int i = 1; i <= N; i++) {
            for (Edge e : V[i].adj) {
                int newDist = V[i].dist + e.weight;
                if (V[e.target].dist > newDist) {
                    return false;
                }
            }
        }
        return true;
    }

    void runIO() {
        in = new Scanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    void run() {
        try {
            in = new Scanner(new File("bellmanford.in"));
            out = new PrintWriter(new File("bellmanford.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        new BellmanFord().runIO();
    }
}