Given an undirected graph with \(N\) vertices and \(M\) edges, you need to delete \(C\) edges, and keep the graph connected. Then we can calculate \(\frac{N\cdot(N-1)}{2}\) shortest distances of pairs of vertices.
You goal is to maximize the \(K\) th maximum distance.

Input Format

First line contains four integers, \(N,M,C,K\).

Each of the next \(M\) lines contains two integers \(u,v,w\), represents an edge between \(u\) and \(v\) which weighted \(w\). It's guaranteed there is no multiple edges or self loops.

Output Format

\(C\) lines, each line contains two integers, represents one deleted edge.

Scoring

If your output is illegal, score is 0, otherwise it will be \(\frac{the\ Kth\ maxinum\ distance}{\sqrt{sum\ of\ weight\ of\ edges\ in\ the\ original\ graph}}\).

Test generation

\(N=512\)

\(M\) of \(i\) th\((1\le i\le 50)\) input file is \(i\cdot 2606+516\)

\(C\) is random selected in range \([1000,M-N]\)

\(K\) is random selected in range \([1,\frac{N\cdot(N-1)}{2}]\)

The graph generation is, first generate a random tree, then add \(M-N+1\) random edges on it.

\(w\) is random selected in range \([1,10^9]\).

Test data will be regenerated with different seeds after the contest.