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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100005

struct Edge{
	Edge(){
		s = t = 0;
		cost = 0;
	}
	Edge(int arg_s,int arg_t,ll arg_cost){
		s = arg_s;
		t = arg_t;
		cost = arg_cost;
	}
	bool operator<(const struct Edge &arg) const{
		if(s != arg.s){
			return s < arg.s;
		}else{
			return t < arg.t;
		}
	}
	int s,t;
	ll cost;
};

struct Info{
	Info(int arg_to,int arg_edge_id,int arg_port = -1){
		to = arg_to;
		edge_id = arg_edge_id;
		port = arg_port;
	}
	int to,edge_id,port;
};

struct Node{

	int parent,edge_id;
	ll W,edge_cost;
};

int V,E,number;
int order[NUM],lowlink[NUM];
int height[NUM],parent[NUM],connector[NUM];
ll sum_weight[NUM];
bool visited[NUM],is_bridge[NUM];
Edge edge[NUM];
Node nodes[NUM];
vector<Info> G[NUM],Group_G[NUM];

int find(int x){
	if(x == parent[x])return x;
	else{
		return parent[x] = find(parent[x]);
	}
}

bool isSame(int x,int y){
	return find(x) == find(y);
}

void unite(int x,int y){
	x = find(x);
	y = find(y);

	if(x == y)return;

	if(height[x] < height[y]){
		parent[x] = y;
	}else{
		parent[y] = x;
		if(height[x] == height[y])height[x]++;
	}
}

void recursive(int node_id){

	order[node_id] = number++;
	lowlink[node_id] = order[node_id];

	int next_node;

	for(int i = 0; i < G[node_id].size(); i++){
		next_node = G[node_id][i].to;

		if(order[next_node] == -1){ //頂点next_nodeをまだ訪れていない

			visited[G[node_id][i].edge_id] = true;
			recursive(next_node);
			lowlink[node_id] = min(lowlink[node_id],lowlink[next_node]);

		}else if(visited[G[node_id][i].edge_id] == false){ //後退辺をまだ通っていない場合
			lowlink[node_id] = min(lowlink[node_id],order[next_node]);
		}
	}
}

//部分木の総コストを計算
ll dfs(int group_id,int parent){

	ll ret = sum_weight[group_id];

	for(int i = 0; i < Group_G[group_id].size(); i++){
		if(Group_G[group_id][i].to == parent){

			nodes[group_id].parent = parent;
			nodes[group_id].edge_id = Group_G[group_id][i].edge_id;
			nodes[group_id].edge_cost = edge[Group_G[group_id][i].edge_id].cost;
			continue;
		}
		ret += dfs(Group_G[group_id][i].to,group_id)+edge[Group_G[group_id][i].edge_id].cost;
	}

	nodes[group_id].W = ret; //部分木の総コスト

	return ret;
}

int main(){

	scanf("%d %d",&V,&E);

	ll sum = 0;

	for(int i = 0; i < E; i++){
		scanf("%d %d %lld",&edge[i].s,&edge[i].t,&edge[i].cost);

		edge[i].s--;
		edge[i].t--;

		sum += edge[i].cost;

		if(edge[i].s > edge[i].t){
			swap(edge[i].s,edge[i].t);
		}

		G[edge[i].s].push_back(Info(edge[i].t,i));
		G[edge[i].t].push_back(Info(edge[i].s,i));
	}

	ll minimum = sum;
	//printf("sum:%lld\n",sum);
	int ans_from,ans_to;

	//1つの辺を削除する場合を調べる
	for(int i = 0; i < E; i++){

		if(minimum > sum-edge[i].cost){
			minimum = sum-edge[i].cost;
			ans_from = edge[i].s;
			ans_to = edge[i].t;
		}
	}

	sort(edge,edge+E);

	number = 0;

	for(int i = 0; i < V; i++){
		order[i] = -1;
		lowlink[i] = -1;
	}

	//★dfsで通らなかった辺が後退辺!!★
	for(int i = 0; i < E; i++){
		visited[i] = false;
	}

	recursive(0);

	int from,to;

	for(int i = 0; i < E; i++){

		is_bridge[i] = false;
	}

	int num_bridge = 0;

	for(int i = 0; i < E; i++){

		from = edge[i].s;
		to = edge[i].t;

		if(order[edge[i].s] > order[edge[i].t]){
			swap(from,to);
		}

		if(order[from] < lowlink[to]){
			num_bridge++;
			is_bridge[i] = true;
		}
	}

	if(num_bridge == 0){
		printf("%d %d\n",ans_from+1,ans_to+1);
		return 0;
	}

	for(int i = 0; i < V; i++){

		parent[i] = i;
		height[i] = 0;
	}

	//union-findでグループ分け
	for(int i = 0; i < E; i++){
		if(is_bridge[i]){
			continue;
		}

		unite(edge[i].s,edge[i].t);
	}

	//グループごとの重さを調べる
	for(int i = 0; i < V; i++){

		sum_weight[i] = 0;
	}
	for(int i = 0; i < E; i++){
		if(isSame(edge[i].s,edge[i].t)){
			sum_weight[find(edge[i].s)] += edge[i].cost;
		}
	}

	//グループ間のエッジを張る(すべて橋のはず)
	for(int i = 0; i < E; i++){

		if(isSame(edge[i].s,edge[i].t)){
			continue;
		}

		Group_G[find(edge[i].s)].push_back(Info(find(edge[i].t),i));
		Group_G[find(edge[i].t)].push_back(Info(find(edge[i].s),i));
	}

	int root;
	//木にする
	for(int i = 0; i < V; i++){
		if(i == find(i)){
			root = i;
			dfs(i,-1);
			break;
		}
	}

	for(int i = 0; i < V; i++){
		if(i != find(i) ||i == root)continue;

		if(minimum > abs(sum-(nodes[i].W+nodes[i].edge_cost)-nodes[i].W)){

			minimum = abs(sum-(nodes[i].W+nodes[i].edge_cost)-nodes[i].W);
			ans_from = min(edge[nodes[i].edge_id].s,edge[nodes[i].edge_id].t);
			ans_to =  max(edge[nodes[i].edge_id].s,edge[nodes[i].edge_id].t);

		}else if(minimum == abs(sum-(nodes[i].W+nodes[i].edge_cost)-nodes[i].W)){

			if(ans_from > min(min(edge[nodes[i].edge_id].s,edge[nodes[i].edge_id].t),nodes[i].parent)){

				ans_from = min(edge[nodes[i].edge_id].s,edge[nodes[i].edge_id].t);
				ans_to =  max(edge[nodes[i].edge_id].s,edge[nodes[i].edge_id].t);

			}else if(ans_from == min(min(edge[nodes[i].edge_id].s,edge[nodes[i].edge_id].t),nodes[i].parent)
					&& ans_to > max(max(edge[nodes[i].edge_id].s,edge[nodes[i].edge_id].t),nodes[i].parent)){

				ans_to = max(edge[nodes[i].edge_id].s,edge[nodes[i].edge_id].t);
			}
		}
	}

	printf("%d %d\n",ans_from+1,ans_to+1);

	return 0;
}