#1191110 (C++17) No.3751 Nonopoly

• 問題: No.3751 Nonopoly
• ユーザー: akua
• 提出日時: 2026-10-02 21:46:38
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 43 ms / 2,000 ms
• コード長: 2,866 bytes
• コンパイル時間: 1,114 ms
• コンパイル使用メモリ: 223,208 KB
• 実行使用メモリ: 9,904 KB
• 最終ジャッジ日時: 2026-10-02 21:46:46
• 合計ジャッジ時間: 7,159 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 50

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0; i<(ll)(n); i++)
#define repi(i,a,b) for(ll i=(ll)(a); i<(ll)(b); i++)
#define all(v) (v).begin(),(v).end()
#define arr(v) (v).rbegin(),(v).rend()
using vi=vector<int>;
using vvi=vector<vi>;

using vll=vector<ll>;
using vvll=vector<vll>;
using P=pair<ll,ll>;
using vp=vector<P>;
using vvp=vector<vp>;
const ll inf=2e18;
template<typename T,typename S> bool chmin(T& a,const S&b){
    return a>b? a=b,1:0;
}

template<typename T,typename S> bool chmax(T& a,const S&b){
    return a<b? a=b,1:0;
}
int mod = 998244353;
//int mod =  100000007;
struct mint {
   int x;
   mint(ll x_ = 0) : x(x_ % mod) {
      if(x < 0) x += mod;
   }
   mint operator-() {
      auto res = *this;
      res.x = (x ? mod - x : 0);
      return res;
   }
   mint& operator+=(mint r) {
      if((x += r.x) >= mod) x -= mod;
      return *this;
   }
   mint& operator-=(mint r) {
      if((x -= r.x) < 0) x += mod;
      return *this;
   }
   mint& operator*=(mint r) {
      x = 1LL * x * r.x % mod;
      return *this;
   }
   mint& operator/=(mint r) { return *this *= r.inv(); }
   friend mint operator+(mint a, mint b) { return a += b; }
   friend mint operator-(mint a, mint b) { return a -= b; }
   friend mint operator*(mint a, mint b) { return a *= b; }
   friend mint operator/(mint a, mint b) { return a /= b; }
   mint inv() const { return pow(mod - 2); }
   mint pow(ll b) const {
      mint a = *this, c = 1;
      while(b) {
         if(b & 1) c *= a;
         a *= a;
         b >>= 1;
      }
      return c;
   }
};
using vm = vector<mint>;
using vvm = vector<vm>;

constexpr int MAX = 500050;
ll fact[MAX], finv[MAX], invv[MAX];
void initcomb() {
   fact[0] = fact[1] = 1;
   finv[0] = finv[1] = 1;
   invv[1] = 1;
   for(int i = 2; i < MAX; i++) {
      fact[i] = fact[i - 1] * i % mod;
      invv[i] = mod - invv[mod % i] * (mod / i) % mod;
      finv[i] = finv[i - 1] * invv[i] % mod;
   }
}
ll comb(ll n, ll k) {
   if(n < k) return 0;
   if(n < 0 || k < 0) return 0;
   return fact[n] * (finv[k] * finv[n - k] % mod) % mod;
}

/*
int main() {
  string s = "187821878218782187821878218782";
  __int128 x = parse(s);
  x *= 2;
  cout << x << endl;
}
*/
ll gcdll(ll x, ll y) {
   if(y == 0) return x;
   return gcdll(y, x % y);
}

void solve(int test){
    int n,m; cin >> n >> m;
    vll u(m),v(m),w(m);
    vll val(n);
    rep(i,m){
        cin >> u[i] >> v[i] >> w[i];
        u[i]--,v[i]--;
        val[u[i]]+=w[i];
        val[v[i]]+=w[i];
    }
    sort(arr(val));
    ll ans=0;
    rep(i,n){
        if(i%2==0){
            ans+=val[i];
        }
        else {
            ans-=val[i];
        }
    }
    ans/=2;
    cout << ans << endl;









}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t=1; //cin >> t;
    rep(test,t)solve(test);
}