Батьки подарували Роману неорієнтований зв'язний зважений граф з вершинами та ребрами. Роман бажає знайти сумарну довжину усіх шляхів у графі. Довжина шляху дорівнює сумі довжин ребер в ньому. Роман вважає, що шлях з в такий же самий, як і з в , тому він ці шляхи не розрізняє.
Перший рядок містить кількість вершин у графі . Наступні рядків описують ребра. Кожний рядок містить три цілі числа: номери вершин, сполучені ребром (вершини пронумеровані числами від до ), та вагу ребра.
Вивести суму довжин усіх шляхів, обчислену за модулем .