题意：国王本来有一个铺路计划，后来发现太贵了，决定删除计划中的某些边，但是有2个原则，1：所有的城市必须能达到。 2：城市与首都（1号城市）之间的最小距离不能变大。 并且在这2个原则下使得建路消耗最小。
题解：现在来分析一下，使得n个点联通至少需要n-1条路，然后因为求最小消耗，所以路最多也就只有n-1条，除了首都以外，每一个都市都对应着一条路，我们只需要在dijkstra求最短路的时候，每次更新最短路的距离就更新这个点所对应的边，最后每个城市的点对应的边就是符合要求的边，最后求和一下就是答案了。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;
#define ll long long
typedef pair<int, int> pll;
const int INF = 0x3f3f3f3f;
const int N = +;
struct Node
{
int nt, to, d, c;
}Edge[N*];
int head[N], dis[N], pre[N];
int cnt = , n, m;
void add(int u, int v, int d, int c)
{
Edge[cnt].to = v;
Edge[cnt].d = d;
Edge[cnt].c = c;
Edge[cnt].nt = head[u];
head[u] = cnt++;
}
void dijkstra()
{
memset(dis, INF, sizeof(dis));
dis[] = ;
priority_queue<pll, vector<pll>, greater<pll> > q;
q.push(pll(,));
while(!q.empty())
{
int u = q.top().second, d = q.top().first;
q.pop();
if(dis[u] != d) continue;
for(int i = head[u]; ~i; i = Edge[i].nt)
{
int v = Edge[i].to;
if(dis[v] > dis[u] + Edge[i].d)
{
dis[v] = dis[u] + Edge[i].d;
pre[v] = i;
q.push(pll(dis[v],v));
}
else if(dis[v] == dis[u]+Edge[i].d && Edge[i].c < Edge[pre[v]].c)
{
pre[v] = i;
q.push(pll(dis[v],v));
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
while(cin >> n >> m, n+m)
{
memset(head, -, sizeof(head));
cnt = ;
int x, y, d, c;
for(int i = ; i < m; i++)
{
cin >> x >> y >> d >> c;
add(x,y,d,c);
add(y,x,d,c);
}
dijkstra();
ll ans = ;
for(int i = ; i <= n; i++)
{
ans += Edge[pre[i]].c;
}
cout << ans << endl;
}
return ;
}