Educational Codeforces Round 54 (Rated for Div. 2) D. Edge Deletion(dijkstra+bfs)

#include <bits/stdc++.h>
#define maxn 300005
#define inf 1e18
#define ll long long
using namespace std;
struct Node{
	int to,next,id;
	ll w;
	bool operator < (const Node &a) const {
		return a.w < w;
	}
}Edge[maxn << 1],Now,Next;
int head[maxn],num;
ll dist[maxn];
bool vis[maxn];
vector<int> v;
int n,m,k;

void init(){
	memset(head,-1,sizeof(head));
	num = 0;
}

void add(int u, int v,ll w,int id){
	Edge[num].to = v;
	Edge[num].w = w;
	Edge[num].id = id;
	Edge[num].next = head[u];
	head[u] = num ++;
}

void dijkstra(){
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=n;i++) dist[i] = inf;
	priority_queue<Node> q;
	Now.to = 1;
	dist[1] = 0;
	q.push(Now);
	while(!q.empty()){
		Now = q.top();
		q.pop();
		int ans = Now.to;
		if(vis[ans]) continue;
		vis[ans] = true;
		for(int i=head[ans];i!=-1;i=Edge[i].next){
			int to = Edge[i].to;
			if(!vis[to] && dist[to] > dist[ans] + Edge[i].w){
				dist[to] = dist[ans] + Edge[i].w;
				Next.to = to;
				Next.w = dist[to];
				q.push(Next);
			}
		}
	}
}

void solve(){
	memset(vis,false,sizeof(vis));
	vis[1] = true;
	queue<int> q;
	q.push(1);
	while(!q.empty()){
		int ans = q.front();
		q.pop();
		for(int i=head[ans];i!=-1;i=Edge[i].next){
			int to = Edge[i].to;
			if(!vis[to] && dist[to] == dist[ans] + Edge[i].w){
				vis[to] = true;
				dist[to] = dist[ans] + Edge[i].w;
				v.push_back(Edge[i].id);
				q.push(to);
			}
		}
	}
}

int main()
{
	init();
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++){
		int u,v;
		ll w;
		scanf("%d%d%lld",&u,&v,&w);
		add(u, v, w, i);
		add(v, u, w, i);
	}
	dijkstra();
	solve();
	int cnt = v.size();
	if(cnt > k) cnt = k;
	printf("%d\n",cnt);
	for(int i=0;i<cnt;i++){
		printf("%d%c",v[i],i==cnt-1?'\n':' ');
	}
	return 0;
}