Problem: E: Balanced Edge Deletion

problem

Given a weighted simple undirected graph G of N vertices and M edges. The vertices are numbered from 1 to N and the edges are numbered from 1 to M. The i-th edge connects the vertices u_i and v_i, and its cost is w_i.

Consider performing the following operation only once for this graph.

* Select one edge from the set of edges in G and delete that edge.



Since the graph may be divided by the above operation, the graph after the operation will be referred to as A and B. (If not split, B is an empty graph.) Let W (X) be the sum of the costs of the edges in graph X (W (X) = 0 if there are no edges in the graph) and $ \ mathrm Define {cost} $ (A, B) = | W (A) −W (B) |. Find the edge (u, v) that minimizes $ \ mathrm {cost} $ (A, B). If there are more than one, answer the one with the smallest u. If there are still more than one, answer the one with the smallest v.

Input format

The input is given in the following format:


N M
u_1 v_1 w_1
...
u_M v_M w_M


Constraint

* 2 \ leq N \ leq 10 ^ 5
* 1 \ leq M \ leq 10 ^ 5
* 1 \ leq u_i <v_i \ leq N
* If i \ neq j, u_i \ neq u_j or v_i \ neq v_j
* 1 \ leq w_i \ leq 10 ^ 9



The graph given is concatenated.

Output format

Output the answer side to one line separated by blanks as shown below.


u v

* u, v are integers
* 1 \ leq u, v \ leq N



Input example 1


5 4
1 2 1
2 3 10
3 4 5
4 5 1


Output example 1


twenty three

Input example 2


10 11
1 2 1
2 3 10
1 5 2
3 4 7
3 5 9
5 6 8
6 7 5
6 8 3
7 8 12
7 9 1
9 10 8


Output example 2


5 6





Example

Input

5 4
1 2 1
2 3 10
3 4 5
4 5 1


Output

2 3

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<55)+1e9; // ~ 3.6 * 1e16
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
using T = tuple<Int,Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> &a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
template<class T>void prArr(T a,string s=" "){Int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}

class BridgeArticulation{
public:
  int V;
  vector<vector<int> > G;
  vector<int> ord;           //ord[i] := ノードiに訪れた順番
  vector<int> low;           //low[i] := ノードiから訪れることができる最小のord[j]の値。
  vector<int> articulation;
  int ok;
  
  BridgeArticulation():V(-1),ok(false){};
  BridgeArticulation(int V):V(V),G(V),ok(false){};
  
  void add_edge(int a,int b){
    ok = false;
    assert(a < V && b < V);
    assert(a >=0 && b >= 0);
    G[a].push_back(b);
    G[b].push_back(a);
  }
  
  void build(int start = 0){
    ok = true;
    ord.clear(); ord.resize(V,-1);
    low.clear(); low.resize(V,-1);
    articulation.clear(); articulation.resize(V,0);
    
    int cnt = 0;
    function<int(int,int)> dfs=[&](int pos,int pre){
      ord[pos] = low[pos] = cnt++;
      for(int to:G[pos]) {
        if(to == pre) continue; 
        if(ord[to] != -1) low[pos] = min(low[pos], ord[to]);
        else {
          low[pos] = min(low[pos], dfs(to, pos));
          
          if(pos == start) articulation[pos]++;
          else articulation[pos] |= ord[pos] <= low[to];
        }
      }
      if(pos == start) articulation[pos] = articulation[pos] >= 2;
      return low[pos];
    };
    
    dfs(start , -1);

  }

  int isBridge(int a,int b){
    assert(ok);
    assert(a < V && b < V);
    assert(a >= 0 && b >= 0);
    if(ord[a] > ord[b]) swap(a, b);
    return ord[a] < low[b];
  }
  
  int isArticulation(int a){
    assert(ok);
    assert(a >= 0 && a < V);
    return articulation[a];
  }
};

class BCC{
public:
  Int V;
  Int K;
  BridgeArticulation B;
  vector<vector<Int> > G;
  vector<vector<Int> > T;
  vector<Int> par;
  vector<Int> cmp;
  vector<Int> used;

  BCC():V(-1){}
  BCC(Int V):V(V), B(V), G(V){}

  void add_edge(Int a,Int b){
    B.add_edge(a, b);
    G[a].push_back(b);
    G[b].push_back(a);
  }

  void dfs(Int pos){
    if(used[pos]++) return;
    cmp[pos] = K;
    for(Int nx:G[pos]) if(!B.isBridge(pos, nx)) dfs(nx);
  }

  Int bcc(bool makeT = 0){
    B.build();
    used.clear(); used.resize(V, 0);
    cmp.clear(); cmp.resize(V, 0);
    K = 0;
    for(Int i=0;i<V;i++) if(used[i] == 0) dfs(i), K++;
    if(makeT) makeTree();
    return K;
  }

  void makeTree(Int pos = -1, Int pre = -1){
    if(pos == -1){
      T.clear(); T.resize(K);
      par.clear();par.resize(K);
      for(Int i=0;i<V;i++){
	set<Int> used;
	for(Int nx:G[i]){
	  Int a = cmp[i], b = cmp[nx];
	  if(a != b && !used.count(b)) T[a].push_back(cmp[nx]), used.insert(b); 
	}
      }
      for(Int i=0;i<K;i++) if(par[i] == -1) makeTree(i, -1);
      return;
    }
    par[pos] = pre;
    for(Int nx:T[pos]) if(nx != pre) makeTree(nx, pos);
  }
};

signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int N, M;
  cin>>N>>M;

  vector<vector<P> > G(N);
  BCC bcc(N);
  Int all = 0;

  map<P,Int> ecost;
  for(Int i=0;i<M;i++){
    Int a, b, c;
    cin>>a>>b>>c; a--, b--;
    bcc.add_edge(a, b);
    G[a].push_back(P(b, c));
    G[b].push_back(P(a, c));
    ecost[P(a, b)] = c;
    ecost[P(b, a)] = c;
    all += c;
  }

  using Tu = tuple<Int,Int,Int>;
  Tu ans = Tu(INF, 0, 1);

  for(int i=0;i<N;i++)
    for(P p:G[i]){
      int to = p.first;
      int cost = p.second;
      if(i > to) continue;
      ans = min(ans, Tu(all - cost, i, to));
    }
  

  Int n = bcc.bcc(1);
  vector<Int> sum(n);

  using T = tuple<Int,Int,Int,Int> ;
  set<T> bedge;
  for(Int i=0;i<N;i++)
    for(auto p:G[i]){
      Int to, cost; tie(to, cost) = p;
      if(i > to) continue;
      if(bcc.cmp[i] != bcc.cmp[to]) {
	bedge.insert(T(bcc.cmp[i], bcc.cmp[to], i, to));
	bedge.insert(T(bcc.cmp[to], bcc.cmp[i], to, i));
      }
      else sum[bcc.cmp[i]] += cost;
    }

  
  
  auto g = bcc.T;
  function<Int(Int,Int)> dfs= [&](Int pos,Int pre){

    Int res = sum[pos];
    
    for(Int to:g[pos]){
      if(to == pre) continue;
      Int a, b, u, v;tie(a, b, u, v) = *bedge.lower_bound(T(pos, to, -1, -1));
      assert(a == pos && to == b);
      Int cost =  ecost[P(u, v)];
      Int s = dfs(to, pos);
      Int t = all - cost - s;
      ans = min(ans, Tu(abs(s - t), min(u, v), max(u, v)));
      res += s + cost;
    }
    return res;
  };

  dfs(0, -1);
  Int val,u, v;
  tie(val, u, v) = ans;
  //cout<<val<<endl;
  cout<<u+1<<" "<<v+1<<endl;

  return 0;
}