import argparse, math, sys
from Queue import PriorityQueue


# PART A: Fill in below the code for disjktra
def dijkstra(G, source):
    n = G.get_size()[0]
    d = [float("inf")] * n
    p = [-1] * n
    d[source] = 0
    
    q = Heap(n)

    q.decrease_value(source, d[source])
    while q.size() > 0:
        x = q.extract_min()
        for y, dst in G.get_neighbors(x):
            if d[y] > d[x] + dst:
                d[y] = d[x] + dst
                p[y] = x
                q.decrease_value(y, d[y])

    return (d, p)

# PART B: Fill in below the code for part b
def find_path(G, plant, dump):
    (d, p) = dijkstra(G, plant)

    path = []
    q = dump
    while q != plant:
        path.append(q)
        q = p[q]
    path = path.reverse()

    return (d[dump], path)

# PART C: Fill in below the code for part c
def get_closest_k(G, plant, dumps, k):
    (d, p) = disjkstra(G, plant)

    dump_d = []
    for dump in dumps:
        dump_d.append((d[dump], dump))

    dump_d = sorted(dump_d)

    res = []
    for i in range(k):
        res.append(dump_d[i][1])

    return res

# PART D: Fill in below the code for part d
def find_path_least_waste(G, plant, dump):
    # Create new graph
    N, M = G.get_size()
    edges = G.get_edges()
    for i in range(M):
        edges[i][2] = math.log(edges[i][2])

    G_new = Graph(N, edges)

    return find_path(G_new, plant, dump)

######################################
# DO NOT CHANGE CODE BELOW THIS LINE #
######################################

class Graph:
    def __init__(self, N_nodes, edges):
        """
        Given the number of nodes and the set of edges instantiates a Graph object. 

        Args:
            N_nodes: an integer with the number of nodes in the graph
            edges: a list of edges in tuple format (x, y, dist) representing an edge from x to y of lenght dist
        """

        self.N_nodes = N_nodes
        self.edges = edges
        self.neighbors = [[] for i in range(N_nodes)]

        # Create neighbors
        for i in range(len(edges)):
            self.neighbors[edges[i][0]].append((edges[i][1], edges[i][2]))


    def get_size(self):
        """
        Returns the size of the graph as a tuple (number_of_nodes, number_of_edges)

        Args:
            None

        Returns:
            A tuple (number_of_nodes, number_of_edges)
        """
        return (self.N_nodes, len(self.edges))

    def get_edges(self):
        """
        Returns the edges in the graph in tuple form: for edge x->y the tuples is (x, y, distance)

        Args:
            None

        Returns:
            A list of tuples [(x, y, distance), ...]
        """
        return self.edges

    def get_neighbors(self, node):
        """
        Given a node returns the neighbors of that node and the corresponding distance to them

        Args:
            node: the node to be given the neighbors of

        Returns:
            A list of tuples [(y, distance), ...] where y is a neighbor of x and distance is the distance from x to y
        """
        return self.neighbors[node]

class Heap:
    def __init__(self, N_nodes):
        self.N = N_nodes
        self.heap = [0] + [(float("inf"), i) for i in range(N_nodes)]
        self.pos = [i+1 for i in range(N_nodes)]

    def size(self):
        return self.N
    def val_at(self, i):
        return self.heap[i][0]
    def node_at(self, i):
        return self.heap[i][1]
    def where_is(self, node):
        return self.pos[node]
    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
        self.pos[self.node_at(i)] = i
        self.pos[self.node_at(j)] = j

    def heapify_down(self, i):
        if i > self.N:
            return None

        f1 = 2 * i
        f2 = 2 * i + 1

        lowest = i

        if f1 <= self.N and self.val_at(f1) < self.val_at(lowest):
            lowest = f1
        if f2 <= self.N and self.val_at(f2) < self.val_at(lowest):
            lowest = f2

        if lowest != i:
            self.swap(i, lowest)
            self.heapify_down(lowest)

    def heapify_up(self, i):
        if i <= 1:
            return None

        if self.val_at(i) < self.val_at(i // 2):
            self.swap(i, i // 2)
            self.heapify_up(i // 2)

    def decrease_value(self, node, new_val):
        i = self.where_is(node)
        if not (1 <= i and i <= self.N):
            print "You are trying to decrease value of a node that does not exist anymore"
            sys.exit()
        if new_val < self.val_at(i):
            self.heap[i] = (new_val, self.heap[i][1])
            self.heapify_up(i)

    def extract_min(self):
        node = self.heap[1][1]
        self.pos[node] = -1

        self.heap[1] = self.heap[self.N]
        self.pos[self.heap[1][1]] = 1
        self.N -= 1
        self.heapify_down(1)

        return node

def run_from_file(input_file):
    f = open(input_file)
    lines = f.readlines()
    f.close()

    # get graph
    N = int(lines[0].rstrip().split(" ")[0])
    M = int(lines[0].rstrip().split(" ")[1])
    edges = []
    for i in range(1, M + 1):
        s = lines[i].rstrip().split(" ")
        edges.append((int(s[0]), int(s[1]), int(s[2])))

    G = Graph(N, edges)

    (d, p) = dijkstra(G, 0)

    print d
    print p


def run_for_infoarena():
    f = open("dijkstra.in")
    lines = f.readlines()
    f.close()

    # get graph
    N = int(lines[0].rstrip().split(" ")[0])
    M = int(lines[0].rstrip().split(" ")[1])
    edges = []
    for i in range(1, M + 1):
        s = lines[i].rstrip().split(" ")
        edges.append((int(s[0]) - 1, int(s[1]) - 1, int(s[2])))

    G = Graph(N, edges)

    (d, p) = dijkstra(G, 0)

    g = open("dijkstra.out", "w")

    for i in range(1, N):
        g.write(str(d[i]) + " ")

    g.write("\n")
    g.close()


if __name__ == '__main__':
  #import argparse, cProfile
  #parser = argparse.ArgumentParser()
  #parser.add_argument("file")
  #args = parser.parse_args()

  run_for_infoarena()