题意要求我们先求出以一号点为出发点的最短路，那么直接跑一遍 dijkstra，然后把所有点按照最短路长度从小到大排序，枚举每一个前缀计算代价取最小值即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
vector<pair<int,int>> g[N];
int dis[N], vis[N], val[N], a[N], use[N];
signed main()
{
	memset(dis, 0x3f, sizeof dis);
	int n, m, c, now = 0;
	cin >> n >> m >> c;
	for (int i = 1; i <= n; i++)
		a[i] = i;
	while (m--)
	{
		int a, b, d;
		cin >> a >> b >> d;
		g[a].push_back({b, d});
		g[b].push_back({a, d});
		now += d;
	}
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
	dis[1] = 0;
	q.push({0, 1});
	while (!q.empty())
	{
		int u = q.top().second;
		q.pop();
		if (vis[u])
			continue;
		vis[u] = 1;
		for (pair<int,int> i : g[u])
		{
			int v = i.first, w = i.second;
			if (dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				q.push({dis[v], v});
			}
		}
	}
	sort(a + 1, a + 1 + n, [](int x, int y){
		return dis[x] < dis[y];
	});
	int ans = now;
	for (int i = 1; i <= n; i++)
	{
		use[a[i]] = 1;
		for (pair<int,int> j : g[a[i]])
		{
			int v = j.first, w = j.second;
			if (use[v])
				now -= w;
		}
		ans = min(ans, now + c * dis[a[i]]);
	}
	cout << ans;
	return 0;
}