C: Project Management / プロジェクト管理

あなたは凄腕のプロジェクトマネージャである． 今回は超大規模なプロジェクトのマネジメントを請け負った．

C_fig_arrow.png

図1: アローダイアグラム

これまでの勘と経験からなんとか 図1 のようなアローダイアグラムを作成した． 各ノードは作業の結合点を表している． また，Sはプロジェクトの開始状態，Tはプロジェクトの終了状態を表す結合点である． 例えば結合点P3において，作業Gは作業Cと作業Eが終了しなければ開始できない． プロジェクトの計画は完璧であり，全ての結合点は，そこから出て再びその結合点に戻る作業経路を持たない． また，全ての作業は前後に結合点を持っており， 開始状態と終了状態以外の結合点は必ず前後に作業を持っている．

しかし，今回のプロジェクトは作業数が多い．

アローダイアグラムにおいて，所要時間が最長となる経路(クリティカルパス)上の作業は， プロジェクトの時間制約に大きく影響する． そこであなたはアローダイアグラム上のクリティカルパスの所要日数を計算するプログラムを書くことにした． ちなみに，このクリティカリパスは必ずアローダイアグラム上に存在する．

Input

入力は次の形式で表される．

n m
a1 b1 c1
...
am bm cm

n ( 2 ≦ n ≦ 400 ) は結合点の数， m ( 1 ≦ m ≦ 800 ) は作業の数を表す整数である． このとき，結合点 0 が開始状態の結合点を表し，結合点 n - 1 が終了状態の結合点を表している． ai, bi, ci は1つの空白で区切られた整数であり， 結合点 ai ( 0 ≦ ai ≦ n - 2 ) から bi ( 1 ≦ bi ≦ n - 1 ) までの作業に ci ( 1 ≦ ci ≦ 100 ) 日必要なことを表している． ai と bi は常に異なっている． また，同じ ai, bi の組みは2度以上現れないと考えて良い．

Output

クリティカルパスの所要日数を表す整数を1行出力せよ． 出力にはこれら以外の文字があってはならない．

Sample Input 1

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

Sample Output 1

19