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<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e18+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

class nizyu{public:
	//2重辺連結成分分解ライブラリ!!!!!!!
	//SCCみたいにつかいます
	vector<vector<int>>road;//もとの辺
	vector<int>imo;
	vector<int>name;
	vector<bool>used;//訪れた順 こう大変を知ることができる
	vector<bool>uuuu;
	int n,niznum;//niznum=連結成分全体のかず
	nizyu(void){}
	nizyu(int in){n=in;road.res(n);}
	void add_road(int a,int b){road[a].pub(b);road[b].pub(a);}
	void sai_dfs(int ter,int oya){
		name[ter]=niznum;
		//cerr<<"name["<<ter<<"]="<<niznum<<endl;
		for(auto it:road[ter]){
			if(it==oya){continue;}
			if(name[it]!=-1){continue;}
			sai_dfs(it,ter);
		}
	}
	int dfs_tree(int ter,int oya=-1){
		//cerr<<"ter="<<ter<<"oya="<<oya<<endl;
		//dfs木を作る
		if(used[ter]){return 0;}
		used[ter]=true;
		int koutai=0;
		bool che=true;
		for(auto it:road[ter]){
			if(it==oya&&che){che=false;continue;}//一度だけ無効化(来た道なので)
			if(used[it]&&(!uuuu[it])){koutai++;imo[it]++;}
			else{koutai+=dfs_tree(it,ter);}
		}
		koutai-=imo[ter];
		//cerr<<"ter="<<ter<<"koutai="<<koutai<<endl;
		uuuu[ter]=true;
		if(koutai==0){sai_dfs(ter,oya);niznum++;}//橋
		return koutai;
	}
	void do_nizyu(void){
		//二十辺連結成分分解する
		niznum=0;
		imo.res(n);
		used.res(n);
		uuuu.res(n);
		name.res(n);for(auto &it:name){it=-1;}
		for(int i=0;i<n;i++){dfs_tree(i);}
		//for(auto it:name){cerr<<"name="<<it<<endl;}
	}
	vector<vector<int>>Croad;//新しいみち
	void chain_niz(void){
		Croad.res(niznum);
		for(int i=0;i<n;i++){
			for(auto it:road[i]){Croad[name[i]].pub(name[it]);}
		}
		for(int i=0;i<niznum;i++){
			sort(Croad[i].begin(),Croad[i].end());
			Croad[i].erase(unique(Croad[i].begin(),Croad[i].end()),Croad[i].end());
			auto itr=find(Croad[i].begin(),Croad[i].end(),i);
			if(itr!=Croad[i].end()){Croad[i].erase(itr);}
		}
	}
};
vector<vector<pair<int,llint>>>go;
vector<llint>wa;
llint dfs(int ter,int per){
	for(auto it:go[ter]){
		if(it.fir==per){wa[ter]+=it.sec;}
		else{wa[ter]+=dfs(it.fir,ter);}
	}
	return wa[ter];
}
int main(void){
	int n,m,i;cin>>n>>m;
	vector<tuple<int,int,llint>>hen(m);
	nizyu gra(n);
	for(i=0;i<m;i++){
		int u,v;llint w;cin>>u>>v>>w;u--;v--;
		hen[i]=mt(u,v,w);
		gra.add_road(u,v);
	}
	gra.do_nizyu();
	int S=gra.niznum;
	go.res(S);
	wa.res(S);
	for(i=0;i<m;i++){
		int u,v;llint w;tie(u,v,w)=hen[i];
		u=gra.name[u];
		v=gra.name[v];
		if(u==v){wa[u]+=w;}
		else{go[u].pub(mp(v,w));go[v].pub(mp(u,w));}
	}
	dfs(0,-1);
	llint zen=wa[0];
	tuple<llint,int,int>ans=mt(big,0,0);
	//for(i=0;i<S;i++){cerr<<wa[i]<<" ";}cerr<<endl;
	for(i=0;i<m;i++){
		int u,v;llint w;tie(u,v,w)=hen[i];
		int U=u,V=v;
		u=gra.name[u];
		v=gra.name[v];
		if(wa[u]>wa[v]){swap(u,v);}
		if(u==v){mineq(ans,mt(zen-w,U,V));}
		else{mineq(ans,mt(abs(wa[u]-zen+wa[u]-w),U,V));}
	}
	cout<<get<1>(ans)+1<<" "<<get<2>(ans)+1<<endl;
	return 0;
}