M
#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<cstdlib> #include<cmath> #include<stack> #include<map> #include<string> #include<vector> #include<algorithm> using namespace std; #define ll long long #define INF 0x3f3f3f3f #define ull unsigned long long #define endl '\n' const double pi = acos(-1); const int maxn = 1e5 + 10; const int maxm = 2e7 + 10; const ll mod = 1e9 + 7; int n, m, c, d, e, cnt; int head[maxn], vis[maxn]; struct node{ int to; int next; int quan; }edge[maxn << 1]; struct nod{ int u, dis, dep, key; bool operator< (const nod& xgd) const{ return key > xgd.key; } }ans[maxn]; void add(int u, int v, int w){ edge[cnt].to = v; edge[cnt].quan = w; edge[cnt].next = head[u]; head[u] = cnt ++; } int main(){ int u, v, w; scanf("%d %d", &n, &m); scanf("%d %d %d", &c, &d, &e); memset(head, -1, sizeof(head)); for(int i = 1 ; i <= m ; ++ i){ scanf("%d %d %d", &u, &v, &w); add(u, v, w); add(v, u, w); } priority_queue<nod> que; for(int i = 1 ; i <= n ; ++ i) ans[i].key = INF; ans[1].key = 0; que.push(nod{1, 0, 0, 0}); while(!que.empty()){ //puts("44"); nod cur = que.top(); que.pop(); int u = cur.u; if(vis[u]) continue; vis[u] = 1; for(int i = head[u] ; i != -1 ; i = edge[i].next){ int v = edge[i].to; int diss = max(edge[i].quan, ans[u].dis); int depp = ans[u].dep + 1; int keyy = max((diss + d - 1) / d, (depp + e - 1) / e); if(keyy < ans[v].key){ ans[v].key = keyy; ans[v].u = v; ans[v].dis = diss; ans[v].dep = depp; que.push(nod{v, diss, depp, keyy}); } } } cout << ans[n].key * c << endl; return 0; } /* 5 7 1 1 1 1 2 1 1 3 5 1 4 1 2 3 2 2 4 5 3 4 3 3 5 5 */