import java.io.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static class MyScanner {
        private BufferedReader br;
        private StringTokenizer st;

        public MyScanner(Reader reader) {
            br = new BufferedReader(reader);
        }

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

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

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

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

        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public int[] dijkstra(int node, ArrayList<ArrayList<Integer>>[] graph, int[] dist, int[] parent) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));

        pq.add(new int[]{node, dist[node]});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();

            if (cur[1] > dist[cur[0]]) continue;

            for (ArrayList<Integer> next : graph[cur[0]]) {
                if (dist[cur[0]] + next.get(1) < dist[next.get(0)])
                {
                    dist[next.get(0)] = dist[cur[0]] + next.get(1);
                    parent[next.get(0)] = cur[0];

                    pq.add(new int[]{next.get(0), dist[next.get(0)]});
                }
            }
        }

        return dist;
    }

    public void main(String[] args) throws Exception {
        MyScanner scanner = new MyScanner((new FileReader("dijkstra.in")));

        int n, m;
        n = scanner.nextInt();
        m = scanner.nextInt();

        ArrayList<ArrayList<Integer>>[] graph = new ArrayList[n + 1];

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

        for (int i = 0; i < m; i++)
        {
            ArrayList<Integer> lista = new ArrayList<>();
            int a = scanner.nextInt();

            lista.add(0, scanner.nextInt());
            lista.add(1, scanner.nextInt());

            graph[a].add(lista);
        }

        int[] dist = new int[n + 1];
        int[] parent = new int[n + 1];

        for (int i = 1; i <= n; i++)
        {
            dist[i] = Integer.MAX_VALUE;
            parent[i] = -1;
        }

        dist[1] = 0;

        dist = this.dijkstra(1, graph, dist, parent);

        try (BufferedWriter writer = new BufferedWriter(new FileWriter("dijkstra.out"))) {
            for (int i = 1; i <= n; i++)
                writer.write(dist[i] + " ");
        }

    }
}