Under construction

Still being built. Things may change

Coolest Ski Route

Interview

Time limit2sMemory limit512 MB

Summary
Given a DAG of slopes with condition values, find the maximum total condition along any downhill path.
Level

Medium4 of 10

Topics
Graph, Dynamic programming, Topological sort, DFS
Solved
No attempts yet

Problem

John loves winter. Every skiing season he goes heli-skiing with his friends. To do so, they rent a helicopter that flies them directly to any mountain in the Alps. From there they follow the picturesque slopes through the untouched snow.

Of course they want to ski on only the best snow, in the best weather they can get. For this they use a combined condition measure and for any given day, they rate all the available slopes.

Can you help them find the most awesome route?

Input

The input consists of:

  • one line with two integers n (2 ≤ n ≤ 1000) and m (1 ≤ m ≤ 5000), where n is the number of (1-indexed) connecting points between slopes and m is the number of slopes.
  • m lines, each with three integers s, t, c (1 ≤ s, t ≤ n, 1 ≤ c ≤ 100) representing a slope from point s to point t with condition measure c.

Points without incoming slopes are mountain tops with beautiful scenery, points without outgoing slopes are valleys. The helicopter can land on every connecting point, so the friends can start and end their tour at any point they want. All slopes go downhill, so regardless of where they start, they cannot reach the same point again after taking any of the slopes.

Output

Output a single number n that is the maximum sum of condition measures along a path that the friends could take.

Hint

Figure C.1: Map of the second sample case

Examples2

  1. Example 1

    Input
    5 5
1 2 15
2 3 12
1 4 17
4 2 11
5 4 9
    Expected output
    40

  2. Example 2

    Input
    6 6
1 2 2
4 5 2
2 3 3
1 3 2
5 6 2
1 2 4
    Expected output
    7