#include #include #include #include #include using namespace std ; const int MAXN = 1e6 ; const int MAXE = 1e6 ; const long long HIPENALTY = 100000 ; long long N, M, K, W, WW, KK ; typedef pair pli ; char isspec[MAXN] ; int av[MAXE], bv[MAXE] ; long long cv[MAXE] ; int uf[MAXN] ; int leader(int n) { if (uf[n] == -1) return n ; return uf[n] = leader(uf[n]) ; } int main(int argc, char *argv[]) { cin >> N >> M >> K >> W ; int v, a, b, c ; for (int i=0; i> v ; v-- ; isspec[v] = 1 ; } vector unsp, sp, all ; for (int i=0; i> a >> b >> c ; a-- ; b-- ; av[i] = a ; bv[i] = b ; cv[i] = 2LL * c ; if (isspec[a] == isspec[b]) unsp.push_back(make_pair(cv[i], i)) ; else sp.push_back(make_pair(cv[i], i)) ; } sort(unsp.begin(), unsp.end()) ; sort(sp.begin(), sp.end()) ; long long hi = 2 * (HIPENALTY + 100) ; long long lo = - hi ; long long r = INT_MAX ; long long hiside = 0 ; long long loside = 0 ; while (hi >= lo) { long long mid = (hi + lo) >> 1 ; for (int i=0; i 1) cout << "At penalty " << mid << " saw " << sn << " of " << W << " cost " << (cst >> 1) << " e " << (cst >> 1) + ((mid >> 1) * (sn - W)) << endl ; if (en < N-1) { cout << -1 << endl ; exit(0) ; } if (sn < W) { hiside = (cst >> 1) + (mid >> 1) * (sn - W) ; hi = mid - 1 ; } else if (sn > W) { loside = (cst >> 1) + (mid >> 1) * (sn - W) ; lo = mid + 1 ; } else { hiside = loside = cst >> 1 ; if (argc > 1) cout << "Possible solution at " << r << endl ; if (mid > 0) hi = mid - 1 ; else lo = mid + 1 ; break ; } } if (hiside == 0 || loside == 0) r = -4 ; else r = hiside ; if (argc > 1) cout << "loside " << loside << " hiside " << hiside << endl ; if (r < -1) { r = -1 ; } cout << r << endl ; }