dikjstra.py

adj = {}
w = {}
Q = set()
S = []


def populate_w(v1, v2, f):
        w[(v1, v2)] = f


def populate_adj(v1, v2):
	if (v1 in adj):
		adj[v1].add(v2)
	else:
		adj[v1] = set()
		adj[v1].add(v2)
	
	if (v2 in adj):
		adj[v2].add(v1)
	else:
		adj[v2] = set()
		adj[v2].add(v1)

V, E = map(int, raw_input().split())
V += 1
dis = V * [float("+infinity")]
prev = V * [None]

def min_dis(u):
	mini = float("+infinity")
	vertice = None
	for i in adj[u]:
		if ((u, i) in w and vertice == None):
			vertice = i
			mini = w[(u, i)]
		elif ((u, i) in w and mini > w[(u, i)]):
			vertice = i
			mini = w[(u,i)]
	return vertice

	
for i in xrange(E):
	v1, v2, f = map(int, raw_input().split())
	populate_w(v1, v2, f)
	populate_adj(v1, v2)
	Q.add(v1)
	Q.add(v2)

def dijkstra(start, end):
	dis[start] = 0
	
	u = start
	while (len(Q) > 0):
		for v in adj[u]:
			print dis[u]
						
			if ((u, v) in w and (dis[u] + w[(u, v)]) < dis[v]):
				dis[v] = dis[u] + w[(u, v)]
				prev[v] = u

		u = min_dis(u)
		Q.remove(u)
	return prev


print dijkstra(1, V)