Minimum Product Spanning Tree

Given an undirected graph with n nodes and m edges. Each edge i has two weights \(a_i\) and \(b_i\). Your task is to choose a spanning tree \(T\) (a set of \(n-1\) edges connecting all nodes without cycles) such that

[ \left(\sum_{e\in T}a_e\right) \times \left(\sum_{e\in T}b_e\right) ]

is minimized. If there are multiple solutions, output any one of them.

Note: The edges are numbered from 1 to m in the order of input.

inputFormat

The first line contains two integers \(n\) and \(m\) \((2 \le n \le 15,\ m \ge n-1)\), representing the number of nodes and edges.

Then \(m\) lines follow. The \(i\)-th line contains four integers \(u_i, v_i, a_i, b_i\), denoting an undirected edge connecting nodes \(u_i\) and \(v_i\) with weights \(a_i\) and \(b_i\) respectively.

outputFormat

Output \(n-1\) integers in a single line representing the indices of the edges chosen in the spanning tree, separated by spaces. The order of the indices does not matter.

sample

3 3
1 2 1 3
2 3 2 1
1 3 3 2

1 2