You are given an undirected connected graph on $n$ vertices and $m$ edges. For each edge, you know the cost of deletion. You want to delete as many edges as possible so that the graph remains connected and the total cost of deleted edges does not exceed $s$.

The first line of the input contains three integers $n, m, s\ (2 ≤n≤ 50 ,000,\ 1 ≤m≤ 100 ,000,\ 0 ≤s≤ 10^{18})$ — the number of vertices, the number of edges and the total provided cost, respectively.

Next $m$ lines contain a description of the edges, one per line. Each description consists of three integers — the ends of the edge and the cost of deletion that does not exceed $10^9$. There are no multi edges or loops in the graph.

The first line of the output should contain the maximal number of deleted edges. 

The second line should contain the indices of the deleted edges. The edges are indexed from one and respect the input order.