Problem Background

This place is beautiful Nanjing; this place is the charming Jinxiang River; this place is the tranquil Tiger Bridge.

If the beauty of Jinxiang River lies in its picturesque scenery, it might be more accurate to say it is the delightful classical alley-style life of Nanjing that truly makes it beautiful. If the charm of Jinxiang River is in its simple folk customs, it might be more accurate to say it is the secrets buried by history that attract people's curious hearts.

Perhaps many still remember the Tiger Bridge Prison, the largest prison in the Jiangnan region during the Beiyang period, which, over nearly a century, faced the vicissitudes of the Qing, Beiyang, Republic of China, and New China, with its name changing repeatedly, reflecting its profound history.

Nowadays, people might find it hard to believe how many thrilling events once unfolded here.

Problem Description

It was the winter of 1948. A small squad from the Nanjing underground organization decided to launch a surprise attack on Tiger Bridge Prison to rescue the hundreds of people trapped inside. At that time, the prison was surrounded by N layers of electric fences, numbered from the innermost to the outermost as 1, 2, ..., N. The first layer of electric fence was electrified with high voltage. There were M high-voltage lines connecting all the electric fences, with the i-th line connecting the ai-th and bi-th layers of electric fences. To sabotage the i-th high-voltage line, at least Ti agents were needed. Faced with so many layers of electric fences, the surprise attack squad was at a loss. At least one layer of electric fence needed to be destroyed for the surprise attack to succeed.

However, cunning spies got wind of this and, to sabotage the surprise attack plan, secretly added another high-voltage line without the squad's knowledge.

To ensure the success of the surprise attack, regardless of which two layers of electric fences the new secret high-voltage line connected, the squad had to destroy exactly one high-voltage line to ensure at least one layer of electric fence was not electrified. Note that we do not know how many agents are needed to successfully sabotage the new high-voltage line. The question now is, what is the minimum number of agents the surprise attack squad needs?

The decisive battle is tonight!

Input Format

The first line contains two integers, N and M, representing the number of electric fence layers and the number of high-voltage lines, respectively.
The following M lines each contain three integers, ai, bi, and Ti.

Output Format

Output a single line containing an integer, representing the minimum number of agents needed. If the plan is bound to fail, output -1.

Sample Input and Output

Sample Input #1

3 2
1 2 1
2 3 2

Sample Output #1

-1

Sample Input #2

4 3
1 2 1
1 3 2
1 4 3

Sample Output #2

3

Notes

For 30% of the data, N ≤ 200, M ≤ 250.
For 70% of the data, N ≤ 50000, M ≤ 100000.
For 100% of the data, N ≤ 500000, M ≤ 1000000, T ≤ 100000.

For the second sample, the new high-voltage line could only be between layers 2 and 3, 2 and 4, or 3 and 4.

If it is between 2 and 3, only the high-voltage line between 1 and 4 can be destroyed; if it is between 2 and 4, only the high-voltage line between 1 and 3 can be destroyed; if it is between 3 and 4, only the high-voltage line between 1 and 2 can be destroyed.

Therefore, at least 3 agents are needed to handle all possible scenarios.

见题面 Input 部分

见题面 Output 部分