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 <cstddef>
#include <tuple>
#include <stack>
#include <algorithm>
#include <iostream>
#include <vector>
namespace loquat {
using vertex_t = size_t;
}
namespace loquat {
namespace edge_param {
struct to_ {
	vertex_t to;
	explicit to_(vertex_t t = 0)
		: to(t)
	{ }
};
template <typename T>
struct weight_ {
	using weight_type = T;
	weight_type weight;
	explicit weight_(const weight_type& w = weight_type())
		: weight(w)
	{ }
};
template <typename T>
using weight = weight_<T>;
}
namespace detail {
template <typename T, typename... Params>
struct edge_param_wrapper : public T, edge_param_wrapper<Params...> {
	template <typename U, typename... Args>
	explicit edge_param_wrapper(U&& x, Args&&... args)
		: T(std::forward<U>(x))
		, edge_param_wrapper<Params...>(std::forward<Args>(args)...)
	{ }
};
template <typename T>
struct edge_param_wrapper<T> : public T {
	template <typename U>
	explicit edge_param_wrapper(U&& x)
		: T(std::forward<U>(x))
	{ }
};
}
template <typename... Params>
struct edge : public detail::edge_param_wrapper<edge_param::to_, Params...> {
	template <typename... Args>
	explicit edge(Args&&... args)
		: detail::edge_param_wrapper<edge_param::to_, Params...>(
			std::forward<Args>(args)...)
	{ }
};
}
namespace loquat {
template <typename EdgeType>
class adjacency_list {
public:
	using edge_type = EdgeType;
	using edge_list = std::vector<edge_type>;
private:
	std::vector<std::vector<EdgeType>> m_edges;
public:
	explicit adjacency_list(size_t n)
		: m_edges(n)
	{ }
	size_t size() const {
		return m_edges.size();
	}
	const edge_list& operator[](vertex_t u) const {
		return m_edges[u];
	}
	edge_list& operator[](vertex_t u){
		return m_edges[u];
	}
	template <typename... Args>
	void add_edge(vertex_t from, Args&&... args){
		m_edges[from].emplace_back(std::forward<Args>(args)...);
	}
};
}
namespace loquat {
class disjoint_set {
public:
	using value_type = size_t;
private:
	std::vector<value_type> m_parents;
	std::vector<value_type> m_ranks;
public:
	explicit disjoint_set(size_t n)
		: m_parents(n)
		, m_ranks(n)
	{
		for(size_t i = 0; i < n; ++i){
			m_parents[i] = i;
		}
	}
	value_type find(size_t x){
		if(m_parents[x] == x){ return x; }
		m_parents[x] = find(m_parents[x]);
		return m_parents[x];
	}
	value_type unite(size_t x, size_t y){
		x = find(x);
		y = find(y);
		if(x == y){ return x; }
		if(m_ranks[x] < m_ranks[y]){
			m_parents[x] = y;
			return y;
		}else if(m_ranks[x] > m_ranks[y]){
			m_parents[y] = x;
			return x;
		}else{
			m_parents[y] = x;
			++m_ranks[x];
			return x;
		}
	}
};
}
namespace loquat {
using belonging_components_t = std::vector<vertex_t>;
}
namespace loquat {
class low_link {
public:
	using index_type = size_t;
	static constexpr index_type nil = std::numeric_limits<index_type>::max();
private:
	std::vector<index_type> m_ord;
	std::vector<index_type> m_low;
public:
	template <typename EdgeType>
	low_link(const adjacency_list<EdgeType>& g)
		: m_ord(g.size(), std::numeric_limits<index_type>::max())
		, m_low(g.size(), std::numeric_limits<index_type>::max())
	{
		struct frame_type {
			vertex_t u, p;
			size_t i, m;
			frame_type() : u(0), p(0), i(0), m(0) { }
			frame_type(vertex_t u, vertex_t p, size_t i, size_t m)
				: u(u), p(p), i(i), m(m)
			{ }
		};
		const auto nil = std::numeric_limits<vertex_t>::max();
		const auto n = g.size();
		index_type next_ord = 0;
		for(vertex_t root = 0; root < n; ++root){
			if(m_ord[root] != nil){ continue; }
			std::stack<frame_type> frame_stack;
			frame_stack.emplace(root, nil, 0, 0);
			while(!frame_stack.empty()){
				const auto f = frame_stack.top();
				frame_stack.pop();
				if(f.i == 0){
					if(m_ord[f.u] != nil){ continue; }
					m_ord[f.u] = next_ord++;
				}
				if(f.i < g[f.u].size()){
					const auto v = g[f.u][f.i].to;
					if(v != f.p){
						frame_stack.emplace(f.u, f.p, f.i + 1, f.m);
						frame_stack.emplace(v, f.u, 0, 0);
					}else{
						frame_stack.emplace(f.u, f.p, f.i + 1, f.m + 1);
					}
				}else{
					for(const auto& e : g[f.u]){
						if(e.to == f.p && f.m < 2){ continue; }
						m_low[f.u] = std::min({m_low[f.u], m_low[e.to], m_ord[e.to]});
					}
				}
			}
		}
	}
	index_type ord(vertex_t v) const { return m_ord[v]; }
	index_type low(vertex_t v) const { return m_low[v]; }
};
}
namespace loquat {
template <typename EdgeType>
belonging_components_t biconnected_components(
	const adjacency_list<EdgeType>& graph)
{
	const auto nil = low_link::nil;
	const auto n = graph.size();
	const low_link ll(graph);
	std::vector<vertex_t> ord2vertex(n);
	for(vertex_t v = 0; v < n; ++v){ ord2vertex[ll.ord(v)] = v; }
	disjoint_set ds(n);
	for(vertex_t u = 0; u < n; ++u){
		if(ll.low(u) > ll.ord(u)){ continue; }
		const auto v = ord2vertex[ll.low(u)];
		ds.unite(u, v);
	}
	belonging_components_t bcc(n, nil);
	for(vertex_t v = 0; v < n; ++v){ bcc[v] = ds.find(v); }
	return bcc;
}
}
using namespace std;
using ll = long long;
using tlii = tuple<ll, int, int>;
using edge = loquat::edge<loquat::edge_param::weight<int>>;
static const ll INF = 1000000000000000000ll;
ll recur(
	vector<ll>& subtree_sums,
	int u, int p,
	const loquat::adjacency_list<edge>& g,
	const vector<ll>& group_sums)
{
	ll sum = group_sums[u];
	for(const auto& e : g[u]){
		if(e.to == p){ continue; }
		sum += e.weight + recur(subtree_sums, e.to, u, g, group_sums);
	}
	subtree_sums[u] = sum;
	return sum;
}
int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	loquat::adjacency_list<edge> g(n);
	ll weight_sum = 0;
	for(int i = 0; i < m; ++i){
		int u, v, w;
		cin >> u >> v >> w;
		--u; --v;
		g.add_edge(u, v, w);
		g.add_edge(v, u, w);
		weight_sum += w;
	}
	tlii answer(INF, 0, 0);
	for(int u = 0; u < n; ++u){
		for(const auto& e : g[u]){
			answer = min(answer, tlii(weight_sum - e.weight, u, e.to));
		}
	}
	const auto bcc = loquat::biconnected_components(g);
	loquat::adjacency_list<edge> tree(n);
	vector<ll> group_sum(n);
	int root = 0;
	for(int u = 0; u < n; ++u){
		if(bcc[u] == u){ root = u; }
		for(const auto& e : g[u]){
			const int tu = bcc[u], tv = bcc[e.to];
			if(tu == tv && u < e.to){ group_sum[tu] += e.weight; }
			if(tu != tv){ tree.add_edge(tu, tv, e.weight); }
		}
	}
	vector<ll> subtree_sums(n);
	recur(subtree_sums, root, -1, tree, group_sum);
	for(int u = 0; u < n; ++u){
		for(const auto& e : g[u]){
			if(bcc[u] == bcc[e.to] || u >= e.to){ continue; }
			const ll b = min(subtree_sums[bcc[u]], subtree_sums[bcc[e.to]]);
			const ll a = weight_sum - e.weight - b;
			answer = min(answer, tlii(llabs(a - b), u, e.to));
		}
	}
	cout << get<1>(answer) + 1 << " " << get<2>(answer) + 1 << endl;
	return 0;
}