#line 2 "cpplib/util/template.hpp" #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2") #include using namespace std; struct __INIT__{__INIT__(){cin.tie(0);ios::sync_with_stdio(false);cout< vec; typedef vector> mat; typedef vector>> mat3; typedef vector svec; typedef vector> smat; templateusing V=vector; templateusing VV=V>; templateinline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<inline void output2(T t){for(auto i:t)output(i);} templateinline void debug(T t){bool f=0;for(auto i:t){cerr<<(f?" ":"")<inline void debug2(T t){for(auto i:t)output(i);} #define loop(n) for(long long _=0;_<(long long)(n);++_) #define rep(i,...) for(auto i:range(__VA_ARGS__)) #define rrep(i,...) for(auto i:reversed(range(__VA_ARGS__))) #define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i) #define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i) #define irep(i) for(lint i=0;;++i) inline vector range(long long n){if(n<=0)return vector();vectorv(n);iota(v.begin(),v.end(),0LL);return v;} inline vector range(long long a,long long b){if(b<=a)return vector();vectorv(b-a);iota(v.begin(),v.end(),a);return v;} inline vector range(long long a,long long b,long long c){if((b-a+c-1)/c<=0)return vector();vectorv((b-a+c-1)/c);for(int i=0;i<(int)v.size();++i)v[i]=i?v[i-1]+c:a;return v;} templateinline T reversed(T v){reverse(v.begin(),v.end());return v;} #define all(n) begin(n),end(n) templatebool chmin(T& s,const E& t){bool res=s>t;s=min(s,t);return res;} templatebool chmax(T& s,const E& t){bool res=s(s,t);return res;} const vector dx={1,0,-1,0,1,1,-1,-1}; const vector dy={0,1,0,-1,1,-1,1,-1}; #define SUM(v) accumulate(all(v),0LL) templateauto make_vector(T x,int arg,Args ...args){if constexpr(sizeof...(args)==0)return vector(arg,x);else return vector(arg,make_vector(x,args...));} #define extrep(v,...) for(auto v:__MAKE_MAT__({__VA_ARGS__})) vector> __MAKE_MAT__(vector v){if(v.empty())return vector>(1,vector());long long n=v.back();v.pop_back();vector> ret;vector> tmp=__MAKE_MAT__(v);for(auto e:tmp)for(long long i=0;iostream& operator<<(ostream& out,pairv){out<<"("< data; int sz; public: UF(int sz):sz(sz){data.resize(sz,-1);} bool unite(int x,int y){ x=root(x);y=root(y); if(x==y)return 0; if(data[x]>data[y])swap(x,y); data[x]+=data[y]; data[y]=x; sz--; return 1; } inline int root(int x){return data[x]<0?x:data[x]=root(data[x]);} inline bool same(int x, int y){return root(x)==root(y);} inline int size(){return sz;} inline int size(int x){return -data[root(x)];} }; #line 3 "cpplib/math/binary_search_double.hpp" /** * @brief 二分探索(double) */ template long double bs(long double mn,long double mx,F func) { long double left = mn; long double right =mx; for(int i=0;i<100;i++){ long double mid=(right+left)*0.5; if (!func(mid)) right = mid; else left = mid; } return left; } #line 1 "cpplib/util/int128.hpp" std::ostream &operator<<(std::ostream &dest, __int128_t value) { std::ostream::sentry s(dest); if(s){ __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } __int128 parse(string &s) { __int128 ret = 0; for (int i = 0; i < (int)s.length(); i++) if ('0' <= s[i] && s[i] <= '9') ret = 10 * ret + s[i] - '0'; return ret; } std::istream &operator>>(std::istream &dest, __int128_t& value){ string s; dest>>s; value=parse(s); return dest; } #line 5 "code.cpp" //#include"cpplib/util/cpp_int.hpp" int main(){ __int128_t n,m,k; cin>>n>>m>>k; //k*=1'000'000'000'000'000LL; vector<__int128_t> a(m),b(m),c(m),d(m); rep(i,m){ cin>>a[i]>>b[i]>>c[i]>>d[i]; c[i]*=1'000'000'000'000'000LL; a[i]--;b[i]--; } auto g=[&](vector<__int128_t> x){ __int128_t ans=0; rep(i,m){ ans-=d[i]*x[i]; } return ans; }; auto f=[&](vector<__int128_t> x){ vector>v; __int128_t ans=0; rep(i,m){ v.emplace_back(c[i]+x[i],a[i],b[i]); } sort(all(v)); UF uf(n); rep(i,m){ if(uf.unite(get<1>(v[i]),get<2>(v[i]))){ ans+=get<0>(v[i])*k; } } return ans; }; auto p=[&](vector<__int128_t> x){ vector>v; vector<__int128_t>res(m,0); rep(i,m){ v.emplace_back(c[i]+x[i],a[i],b[i],i); } sort(all(v)); UF uf(n); rep(i,m){ if(uf.unite(get<1>(v[i]),get<2>(v[i]))){ res[get<3>(v[i])]=k; } } return res; }; lint cnt=10000; __int128_t pre=0,ans=0; __int128_t aaa; { vector<__int128_t> x(m,0); for(int i=0;i x(m,0); for(int i=0;ians){ cout<<-1<