Given an undirected connected graph with $ n $ vertices and $ m $ edges, where edges have non-negative weights, calculate $ \sum \limits _ {i = 2} ^ n \sum \limits _ {j = 1} ^ {i - 1} dis(i, j) $, where $ dis(i, j) $ denotes the shortest distance between vertex $ i $ and vertex $ j $.

It is guaranteed that $ m - n \le 1000 $.

Input

The first line contains two positive integers $ n $ and $ m $.

The next $ m $ lines each contain three non-negative integers $ u, v, w $, representing an edge between $ u $ and $ v $ with length $ w $. It is guaranteed that there are no multiple edges or self-loops. $ w \le 10 ^ 4 $.

Output

Output a single non-negative integer representing the sum of shortest paths.

Examples

Input 1

5 10
1 5 7
3 4 2
4 5 1
3 2 1
3 5 2
1 3 6
1 4 4
2 1 6
2 4 2
2 5 3

Output 1

32

Subtasks

For all data, $ 2 \le n \le 10 ^ 5 $ and $ m - n \le 1000 $.