题意（说人话）

给定一个无向图，求其生成树的每一个边，使其1号点到各个节点的总距离最小。（写的不好欢迎各位巨佬纠正）

思路

考虑最短路，我用的$Dijkstra$（还不会的出门左转。直接跑一便最短路，记录下来每一个要用的边，最后直接输出即可。

为啥了？

是这样的：注意到如果每一个点都取最短路，就不存在另一个生成树使得其总边权最小，不然他就不叫最短路了。

那为啥一定是个树了？

$Dijkstra$的本质就是让近的点先访问，记录下来长度，以后就不在访问了。既然一个点只访问一次，必然只会有$n-1$条边会用到，自然就是个生成树了。

AC代码

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int> 
#define PIII pair<int,pair<int,int> > 
using namespace std;
const int N=2e5+10;
vector<PII>G[N];
map<PII,int>road;
int dis[N],n,m;
bool v[N],use[N];
void dij()
{
	priority_queue<PIII,vector<PIII>,greater<PIII> >Q;
	memset(dis,0x3f,sizeof(dis));dis[1]=0;
	Q.push({0,{1,0}});
	while(!Q.empty())
	{
		int x=Q.top().second.first,from=Q.top().second.second;Q.pop();
		if(v[x])continue;
		v[x]=1;use[from]=1;
		for(auto i:G[x])
		{
			int y=i.first,w=i.second;
			if(dis[y]>dis[x]+w)
			{
				dis[y]=dis[x]+w;
				Q.push({dis[y],{y,road[{x,y}]}});
			}
		}
	}
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1,x,y,w;i<=m;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&w);
		road[{x,y}]=road[{y,x}]=i;
		G[x].push_back({y,w});
		G[y].push_back({x,w});
	}
	dij();
	for(int i=1;i<=m;i++)if(use[i])printf("%lld ",i);
	return 0;
}