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

public class Main {
    static int INF = 250000001;

    static int n , m;

    public static void main(String[] args) {
        Scanner fin = new Scanner(System.in);
        */
/* FILE INPUT*//*

        try {
            fin = new Scanner(new File("dijkstra.in"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        */
/* FILE OUTPUT*//*

        PrintStream out = null;
        try {
            out = new PrintStream(new FileOutputStream("dijkstra.out"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        System.setOut(out);

        n = fin.nextInt();
        m = fin.nextInt();

        // list of all Vertices / Nodes
        ArrayList<Node> graph= new ArrayList<Node>();
        for (int i=0; i<=n; i++) graph.add(new Node(i));

        // Reading Vertices and Weights
        int a, b, c;
        for (int i=0; i<m; i++){
            a = fin.nextInt();
            b = fin.nextInt();
            c = fin.nextInt();

            graph.get(a).adjList.put(b, c);
        }

        // Djikstra
        PriorityQueue<Node> Q = new PriorityQueue<Node>();

        // initialise nodes in Queue
        graph.get(1).dist = 0;
        for (int i=1; i <= n; i++) Q.offer(graph.get(i));

        while(!Q.isEmpty()){
            Node parent = graph.get(Q.poll().nr);

            for (Map.Entry<Integer, Integer> childNr : parent.adjList.entrySet()){
                Node kid = graph.get(childNr.getKey());
                if (kid.dist > parent.dist + childNr.getValue()){
                    Q.remove(kid);
                    kid.dist = parent.dist + childNr.getValue();
                    Q.add(kid);
                }
            }
        }

        for(int i=2; i<=n; i++) System.out.print(graph.get(i).dist + " ");
    }
}

class Node implements Comparable<Node>{
    public Map<Integer, Integer> adjList = new HashMap<Integer, Integer>();
    public int dist = Main.INF;
    public int nr = 0;

    public Node (int x){
        this.nr = x;
    }

    public int compareTo(Node o) {
        return Integer.compare(this.dist, o.dist);
    }
}
*/

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Vertex implements Comparable<Vertex>
{
    public final String name;
    public Edge[] adjacencies;
    public double minDistance = Double.POSITIVE_INFINITY;
    public Vertex previous;
    public Vertex(String argName) { name = argName; }
    public String toString() { return name; }
    public int compareTo(Vertex other)
    {
        return Double.compare(minDistance, other.minDistance);
    }
}

class Edge
{
    public final Vertex target;
    public final double weight;
    public Edge(Vertex argTarget, double argWeight)
    { target = argTarget; weight = argWeight; }
}

public class Dijkstra
{
    public static void computePaths(Vertex source)
    {
        source.minDistance = 0.;
        PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
        vertexQueue.add(source);

        while (!vertexQueue.isEmpty()) {
            Vertex u = vertexQueue.poll();

            // Visit each edge exiting u
            for (Edge e : u.adjacencies)
            {
                Vertex v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                    vertexQueue.remove(v);
                    v.minDistance = distanceThroughU ;
                    v.previous = u;
                    vertexQueue.add(v);
                }
            }
        }
    }

    public static List<Vertex> getShortestPathTo(Vertex target)
    {
        List<Vertex> path = new ArrayList<Vertex>();
        for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
            path.add(vertex);
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args)
    {
        Vertex v0 = new Vertex("Redvile");
        Vertex v1 = new Vertex("Blueville");
        Vertex v2 = new Vertex("Greenville");
        Vertex v3 = new Vertex("Orangeville");
        Vertex v4 = new Vertex("Purpleville");

        v0.adjacencies = new Edge[]{ new Edge(v1, 5),
                new Edge(v2, 10),
                new Edge(v3, 8) };
        v1.adjacencies = new Edge[]{ new Edge(v0, 5),
                new Edge(v2, 3),
                new Edge(v4, 7) };
        v2.adjacencies = new Edge[]{ new Edge(v0, 10),
                new Edge(v1, 3) };
        v3.adjacencies = new Edge[]{ new Edge(v0, 8),
                new Edge(v4, 2) };
        v4.adjacencies = new Edge[]{ new Edge(v1, 7),
                new Edge(v3, 2) };
        Vertex[] vertices = { v0, v1, v2, v3, v4 };
        computePaths(v0);
        for (Vertex v : vertices)
        {
            System.out.println("Distance to " + v + ": " + v.minDistance);
            List<Vertex> path = getShortestPathTo(v);
            System.out.println("Path: " + path);
        }
    }
}