Ёжик Антон решил отправиться в путешествие по N городам. Но забыл заранее составить план поездки, из-за чего сильно боиться лишних трат, так как чтобы доехать из города \(N_i\) в город \(N_j\) требуется K топлива на каждый километр расстояния между городами. Помогите Антону добраться из 1 города в N-ый город с минимальным количеством затрат.

Описание входных данных

Программа получает на вход целое положительное число N \((1 ≤ N ≤ 10^3)\). Дальше, на следующих N строках идут четыре целых положительных числа: город \(N_i\), \(N_j\) \((1 ≤ N_i, N_j ≤ 10^3)\), расстояние между ними и количества топлива, требуемого на каждый километр расстояния

Описание выходных данных

Программа должна вывести суммарные затраты ёжика на путь из города 1 в город N

Входные данные

7
1 2 5 10
2 3 10 5
3 6 2 9
6 7 7 12
1 4 7 11
4 5 13 3
5 6 10 7

Выхоные данные

202

Примечание

Решение, правильно работающие на числах не превышающие 100, будет оцениваться в 60 баллов.