import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

/**
 * @author: pashka
 */
public class FordBellmanQueue {

    class Edge {
        int src, dst, len;
        public Edge(int src, int dst, int len) {
            this.src = src;
            this.dst = dst;
            this.len = len;
        }
    }

    private void run() throws FileNotFoundException {
        Scanner in = new Scanner(new File("input.txt"));
        int n = in.nextInt();
        int m = in.nextInt();

        List<Edge>[] outgoing = new List[n];
        for (int i = 0; i < n; i++) {
            outgoing[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int src = in.nextInt() - 1;
            int dst = in.nextInt() - 1;
            int len = in.nextInt();
            outgoing[src].add(new Edge(
                    src, dst, len
            ));
        }

        int[] d = new int[n];
        Arrays.fill(d, Integer.MAX_VALUE);
        d[0] = 0;

        Queue<Integer> q = new ArrayDeque<>();
        q.add(0);

        boolean[] inQueue = new boolean[n];
        inQueue[0] = true;
        int c = 0;
        while (q.size() > 0) {
            c++;
            int i = q.poll();
            inQueue[i] = false;
            for (Edge edge : outgoing[i]) {
                if (d[edge.dst] > d[i] + edge.len) {
                    d[edge.dst] = d[i] + edge.len;
                    if (!inQueue[edge.dst]) {
                        q.add(edge.dst);
                        inQueue[edge.dst] = true;
                    }
                }
            }
        }

        System.out.println("Iterations: " + c);
        System.out.println("Distances: " + Arrays.toString(d));
    }

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

}