import java.util.*;
import java.io.*;

public class Main {
    FastScanner 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 run() {
        try {
            in = new FastScanner(new File("cmlsc.in"));
            out = new PrintWriter(new File("cmlsc.out"));

            solve();

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

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

        solve();

        out.close();
    }

    class FastScanner {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public FastScanner(File f) {
            try {
                reader = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }

    public static void main(String[] args) {
        new Main().run();
    }
}