#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long ll; typedef pair P; vector

g[3030]; ll d[3030][3030]; void dfs(int r, int x, int p){ for(auto q:g[x]){ int y=q.first; if(y!=p){ d[r][y]=d[r][x]+q.second; dfs(r, y, x); } } } int main() { int n, q; ll c; cin>>n>>q>>c; for(int i=0; i>u>>v>>l; u--; v--; g[u].push_back({v, l}); g[v].push_back({u, l}); } for(int i=0; i>x[i]; x[i]--; } vector v; for(int i=0; i w[3030]; for(int i=0; iind[t-1]) continue; d2[w[i][j]]=s[ind[t-1]]-s[w[i][j-1]]+c; prev[w[i][j]]=w[i][j-1]; } } ll dp[9100000]; dp[0]=0; for(int i=1; i