Сізге \(n\) бүтін саны берілген — бағытталмаған графтағы төбелердің саны, төбелер \(1\)-ден \(n\)-ға дейін нөмірленген.

Сіз мүмкіндігінше көп қабырғаларды (әрбір төбе жұбы арасында бір ғана қабырға) құрастыруыңыз керек және оларға ерекше бүтін ұзындықтарды тағайындауыңыз қажет, осылайша келесі шарт орындалуы тиіс:

Мүмкін болатын максималды қабырғалар санын табыңыз және осындай графтың мысалын келтіріңіз (яғни, барлық қабырғаларды және олардың ұзындықтарын шығарыңыз).

Енгізу

Кіріс бір жолдан тұрады, онда бір бүтін сан \(n\) (\(2 \le n \le 200\)) бар.

Шығару

Бірінші жолда бір бүтін сан \(m\) — қабырғалардың саны.

Содан кейін \(m\) жолды шығарыңыз, әр жолда үш бүтін сан \(u\), \(v\), \(w\) (\(1 \le u < v \le n\), \(1 \le w \le 2 \cdot 10^5\)) — \(u\) және \(v\) төбелері арасындағы қабырға және оның ұзындығы. Барлық ұзындықтар \(w\) ерекше болуы тиіс.

Егер бірнеше жарамды шешімдер болса, кез келгенін шығарыңыз.

Мысалдар

Енгізу 1

3

Жауап 1

3
1 2 1
2 3 2
1 3 3