5508: 暑期营第八天 牧场行走

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Input

Output

Sample Input Copy

5 3
2 1 1
3 2 2
4 1 4
5 2 8
3 4
3 5
4 5

Sample Output Copy

7
10
13

HINT

对于100%的数据:2≤n,q≤1000