You are given an undirected connected weighted graph consisting of $n$ vertices and $m$ edges. Let's denote the length of the shortest path from vertex $1$ to vertex $i$ as $d_i$. 

You have to erase some edges of the graph so that at most $k$ edges remain. Let's call a vertex $i$ good if there still exists a path from $1$ to $i$ with length $d_i$ after erasing the edges.

Your goal is to erase the edges in such a way that the number of good vertices is maximized.


-----Input-----

The first line contains three integers $n$, $m$ and $k$ ($2 \le n \le 3 \cdot 10^5$, $1 \le m \le 3 \cdot 10^5$, $n - 1 \le m$, $0 \le k \le m$) — the number of vertices and edges in the graph, and the maximum number of edges that can be retained in the graph, respectively.

Then $m$ lines follow, each containing three integers $x$, $y$, $w$ ($1 \le x, y \le n$, $x \ne y$, $1 \le w \le 10^9$), denoting an edge connecting vertices $x$ and $y$ and having weight $w$.

The given graph is connected (any vertex can be reached from any other vertex) and simple (there are no self-loops, and for each unordered pair of vertices there exists at most one edge connecting these vertices).


-----Output-----

In the first line print $e$ — the number of edges that should remain in the graph ($0 \le e \le k$).

In the second line print $e$ distinct integers from $1$ to $m$ — the indices of edges that should remain in the graph. Edges are numbered in the same order they are given in the input. The number of good vertices should be as large as possible.


-----Examples-----
Input
3 3 2
1 2 1
3 2 1
1 3 3

Output
2
1 2 
Input
4 5 2
4 1 8
2 4 1
2 1 3
3 4 9
3 1 5

Output
2
3 2

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Graph algorithms

Shortest paths


Solutions:
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import defaultdict
from math import inf
from heapq import heappop, heappush
ans = []

def dijkstra(start):
	(heap, dist, vis) = ([(0, start, -1)], [inf] * (n + 1), [0] * (n + 1))
	dist[start] = 0
	while heap:
		(d, vertex, index) = heappop(heap)
		if vis[vertex] == 1:
			continue
		vis[vertex] = 1
		if index != -1:
			ans.append(index)
		if len(ans) == min(n - 1, k):
			return ans
		for (child, weight, index) in graph[vertex]:
			weight += d
			if dist[child] > weight:
				dist[child] = weight
				heappush(heap, (weight, child, index))
	return ans
graph = defaultdict(list)
(n, m, k) = map(int, input().split())
for i in range(m):
	(x, y, w) = map(int, input().split())
	graph[x].append((y, w, i + 1))
	graph[y].append((x, w, i + 1))
dijkstra(1)
print(len(ans))
ans = ' '.join(map(str, ans))
sys.stdout.write(ans)


from collections import Counter, defaultdict
import heapq
from sys import stdin, stdout
raw_input = stdin.readline
xrange = range
(n, m, k) = map(int, raw_input().split())
k = min(n - 1, k)
p = [0] * (n + 1)
vis = [0] * (n + 1)
d = [[] for i in xrange(n + 1)]
ans = []
dp = {}
for i in xrange(m):
	(u, v, w) = map(int, raw_input().split())
	d[u].append((v, w))
	d[v].append((u, w))
	dp[u, v] = i + 1
	dp[v, u] = i + 1
q = [(0, 1, 1)]
c = 0
while q:
	(wt, x, par) = heapq.heappop(q)
	if vis[x]:
		continue
	vis[x] = 1
	c += 1
	if par != x:
		ans.append(str(dp[par, x]))
	if c > k:
		break
	for (i, w) in d[x]:
		if not vis[i]:
			heapq.heappush(q, (wt + w, i, x))
print(len(ans))
print(' '.join(ans))


import os
import sys
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
from heapq import *

def main():
	(n, m, k) = map(int, input().split())
	graph = [[] for _ in range(n + 1)]
	for _ in range(m):
		(a, b, c) = map(int, input().split())
		graph[a].append((b, c, _ + 1))
		graph[b].append((a, c, _ + 1))
	dist = [10 ** 15] * (n + 1)
	vis = [0] * (n + 1)
	parent = [0] * (n + 1)
	dist[1] = 0
	hp = [(0, 1)]
	heapify(hp)
	ans = []
	k += 1
	dct = dict()
	dct[1] = -1
	while hp and k:
		(d, x) = heappop(hp)
		if vis[x]:
			continue
		vis[x] = 1
		ans.append(dct[x])
		k -= 1
		for (b, c, id) in graph[x]:
			if not vis[b] and dist[b] > dist[x] + c:
				dist[b] = dist[x] + c
				parent[b] = x
				dct[b] = id
				heappush(hp, (dist[b], b))
	print(len(ans) - 1)
	print(*ans[1:])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os
from io import BytesIO, IOBase
import sys
from heapq import *
from collections import deque
inf = 1000000000000000

def main():
	(n, m, k) = map(int, input().split())
	(tree, dis, v) = ([[] for _ in range(n + 1)], [inf] * (n + 1), [0] * (n + 1))
	for i in range(m):
		(x, y, z) = map(int, input().split())
		z = float(z)
		tree[x].append((y, z, i + 1))
		tree[y].append((x, z, i + 1))
	(dis[1], a, ans) = (0, [(0, 1, 0)], [])
	while a and len(ans) != k:
		(d, node, z) = heappop(a)
		if v[node]:
			continue
		v[node] = 1
		if z:
			ans.append(z)
		if dis[node] < d:
			continue
		for (x, y, z) in tree[node]:
			if dis[x] > d + y:
				dis[x] = d + y
				heappush(a, (d + y, x, z))
	print(len(ans))
	print(*ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
import heapq
from collections import defaultdict
(n, m, k) = list(map(int, input().split()))
edges = defaultdict(list)
dist = [float('inf')] * (n + 1)
dist[1] = 0
pq = []
for i in range(m):
	(x, y, w) = list(map(int, input().split()))
	edges[x].append((i + 1, y, w))
	edges[y].append((i + 1, x, w))
pq = [(0, 1, -1)]
res = []
c = 0
while pq:
	(v, min_e, min_i) = heapq.heappop(pq)
	if dist[min_e] == v:
		if min_i != -1:
			res.append(min_i)
			c += 1
		if c >= n - 1 or c == k:
			break
		for item in edges[min_e]:
			(i, adj, w) = item
			if dist[min_e] + w < dist[adj]:
				dist[adj] = dist[min_e] + w
				heapq.heappush(pq, (dist[adj], adj, i))
print(len(res))
if k > 0:
	print(' '.join(map(str, res)))


import os
import sys
from bisect import bisect_right
from io import BytesIO, IOBase
from math import gcd, inf, sqrt, ceil

def lcm(a, b):
	return a * b // gcd(a, b)

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = Counter()
	while x != 1:
		ret[spf[x]] += 1
		x = x // spf[x]
	return ret

def printDivisors(n):
	i = 2
	z = [1, n]
	while i <= sqrt(n):
		if n % i == 0:
			if n / i == i:
				z.append(i)
			else:
				z.append(i)
				z.append(n // i)
		i = i + 1
	return z

def create(n, x, f):
	pq = len(bin(n)[2:])
	if f == 0:
		tt = min
	else:
		tt = max
	dp = [[inf] * n for _ in range(pq)]
	dp[0] = x
	for i in range(1, pq):
		for j in range(n - (1 << i) + 1):
			dp[i][j] = tt(dp[i - 1][j], dp[i - 1][j + (1 << i - 1)])
	return dp

def enquiry(l, r, dp, f):
	if l > r:
		return inf if not f else -inf
	if f == 1:
		tt = max
	else:
		tt = min
	pq1 = len(bin(r - l + 1)[2:]) - 1
	return tt(dp[pq1][l], dp[pq1][r - (1 << pq1) + 1])

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	x = []
	for i in range(2, n + 1):
		if prime[i]:
			x.append(i)
	return x
import heapq as heap
import sys
input = sys.stdin.readline

def dijkstra(g, n, l):
	ans = []
	(dis, vis) = ([10 ** 20] * (n + 1), [0] * (n + 1))
	dis[1] = 0
	q = [(0, 1, -1)]
	while q:
		(_, i, k) = heap.heappop(q)
		if vis[i] == 1:
			continue
		vis[i] = 1
		if k != -1:
			ans.append(k)
		if len(ans) == l:
			return ans
		for (j, w, k) in g[i]:
			if dis[j] > dis[i] + w:
				dis[j] = dis[i] + w
				heap.heappush(q, (dis[j], j, k))
	return ans

def main():
	(n, m, k) = map(int, input().split())
	adj = [[] for i in range(n + 1)]
	for i in range(m):
		(x, y, w) = map(int, input().split())
		adj[x].append((y, w, i + 1))
		adj[y].append((x, w, i + 1))
	an = dijkstra(adj, n, k)
	print(len(an))
	print(*an)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import heapq as heap
import sys
input = sys.stdin.readline
from math import inf
import gc, os
from os import _exit
gc.disable()

def dijkstra(g, n, l):
	ans = []
	(dis, vis) = ([inf] * (n + 1), [0] * (n + 1))
	dis[1] = 0
	q = [(0, 1, -1)]
	while q:
		(_, i, k) = heap.heappop(q)
		if vis[i] == 1:
			continue
		vis[i] = 1
		if k != -1:
			ans.append(k)
		if len(ans) == l:
			return ans
		for (j, w, k) in g[i]:
			if dis[j] > dis[i] + w:
				dis[j] = dis[i] + w
				heap.heappush(q, (dis[j], j, k))
	return ans
(n, m, k) = map(int, input().split())
g = [[] for i in range(n + 1)]
for i in range(m):
	(x, y, w) = map(int, input().split())
	g[x].append((y, w, i + 1))
	g[y].append((x, w, i + 1))
ans = dijkstra(g, n, k)
print(len(ans))
print(*ans)
sys.stdout.flush()
_exit(0)


import sys
input = sys.stdin.buffer.readline
import heapq
(n, m, k) = map(int, input().split())
k = min(n - 1, k)
graph = [[] for i in range(n)]
edge = {}
for i in range(m):
	(x, y, w) = map(int, input().split())
	edge[x - 1, y - 1] = (w, i)
	edge[y - 1, x - 1] = (w, i)
	graph[x - 1].append(y - 1)
	graph[y - 1].append(x - 1)
ans = []
vis = [0] * n
vis[0] = 1
root = 0
q = []
for i in graph[root]:
	heapq.heappush(q, (edge[i, root][0], root, i))
while len(ans) != k:
	(w, s, e) = heapq.heappop(q)
	if vis[e]:
		continue
	ans.append(edge[s, e][1] + 1)
	vis[e] = 1
	for i in graph[e]:
		if not vis[i]:
			heapq.heappush(q, (w + edge[i, e][0], e, i))
print(len(ans))
print(' '.join(map(str, ans)))


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	from heapq import heappop, heappush
	(n, m, k) = map(int, input().split())
	adj = [[] for _ in range(n)]
	for (i, (u, v, w)) in enumerate((map(int, input().split()) for _ in range(m)), start=1):
		adj[u - 1].append((v - 1, float(w), i))
		adj[v - 1].append((u - 1, float(w), i))
	(inf, eps) = (1e+18, 1e-07)
	dp = [0] + [inf] * (n - 1)
	prev_edge = [-1] * n
	visited = array('b', [1] + [0] * (n - 1))
	(ans_edge, hq) = ([], [])
	for (dest, weight, edge_i) in adj[0]:
		prev_edge[dest] = edge_i
		dp[dest] = weight
		heappush(hq, (weight, dest))
	while k and hq:
		(weight, v) = heappop(hq)
		if visited[v]:
			continue
		ans_edge.append(prev_edge[v])
		visited[v] = 1
		k -= 1
		for (dest, edge_weight, edge_i) in adj[v]:
			if dp[dest] < weight + edge_weight + eps:
				continue
			dp[dest] = weight + edge_weight
			prev_edge[dest] = edge_i
			heappush(hq, (weight + edge_weight, dest))
	sys.stdout.buffer.write(f"{len(ans_edge)}\n{' '.join(map(str, ans_edge))}\n".encode('utf-8'))
main()


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m, k) = map(int, input().split())
g = [[] for i in range(n)]
toid = {}
for i in range(m):
	(x, y, w) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	g[x].append((w, y))
	g[y].append((w, x))
	toid[x, y] = i
	toid[y, x] = i
if k == 0:
	print(0)
	exit()
import heapq
INF = 10 ** 18

def dijkstra(s, edge):
	n = len(edge)
	dist = [INF] * n
	prev = [-1] * n
	dist[s] = 0
	edgelist = []
	heapq.heappush(edgelist, (dist[s], s))
	while edgelist:
		minedge = heapq.heappop(edgelist)
		if dist[minedge[1]] < minedge[0]:
			continue
		v = minedge[1]
		for e in edge[v]:
			if dist[e[1]] > dist[v] + e[0]:
				dist[e[1]] = dist[v] + e[0]
				prev[e[1]] = v
				heapq.heappush(edgelist, (dist[e[1]], e[1]))
	return (dist, prev)
(dist, prev) = dijkstra(0, g)
G = [[] for i in range(n)]
for (i, p) in enumerate(prev):
	if prev[i] != -1:
		G[p].append(i)
s = []
s.append(0)
order = []
while s:
	v = s.pop()
	order.append(v)
	for u in G[v]:
		s.append(u)
ans = []
for v in order:
	for u in G[v]:
		ans.append(toid[v, u] + 1)
		if len(ans) == k:
			break
	else:
		continue
	break
print(len(ans))
print(*ans)


import os, sys
from io import BytesIO, IOBase
from heapq import *

def main():
	(n, m, k) = map(int, input().split())
	path = [[] for _ in range(n)]
	for _ in range(m):
		(u1, v1, w1) = map(int, input().split())
		path[u1 - 1].append((v1 - 1, w1, _ + 1))
		path[v1 - 1].append((u1 - 1, w1, _ + 1))
	visi = [0] + [-1] * (n - 1)
	ans = []
	he = [(i[1], i[0], i[2]) for i in path[0]]
	heapify(he)
	while len(he) and len(ans) != k:
		(w, v, num) = heappop(he)
		if visi[v] != -1:
			continue
		visi[v] = w
		ans.append(num)
		for (to, weight, number) in path[v]:
			if visi[to] == -1:
				heappush(he, (visi[v] + weight, to, number))
	print(len(ans))
	print(*ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()