b210. C. 咒語

/**********************************************************************************/
/*  Problem: b210 "C. 咒語" from 2008 NPSC 高中組決賽                      */
/*  Language: CPP (1187 Bytes)                                                    */
/*  Result: AC(2.8s, 8.3MB) judge by this@ZeroJudge                               */
/*  Author: monkey413 at 2012-07-23 15:10:08                                      */
/**********************************************************************************/


//參考自：https://sites.google.com/a/hpsh.co.cc/code/ti-mu/b210-c
#include<iostream>
#define N 10001
#define swap(a,b){t=a,a=b,b=t;}
using namespace std;
class edge    // 每個點連結出去的邊
{
    public:
        int from ;
        int value ;
};
class node
{
    public:
        edge passage[100] ;
};
node map[N] ;
int top[N]={0} ; // 點的連結個數
unsigned long long int ans[N] ;
int n,m,x,y,z,t,newp;
int main()
{
    while(cin>>n>>m)
    {
        if(!n&&!m) break ;
        for(int i=0 ; i<m ; ++i)
        {
            cin >> x >> y >> z ;
            if(x>y) swap(x,y) ;
            top[y]++ ;
            map[y].passage[top[y]].from=x ;
            map[y].passage[top[y]].value=z ;
        }
        for(int i=1 ; i<=n ; ++i)
        {
            ans[i]=ans[i-1] ; //當沒有點連結到i點時
            for(int j=1 ; j<=top[i] ; ++j)
            {
                newp=ans[map[i].passage[j].from]+map[i].passage[j].value ;
                ans[i]=(ans[i]>newp?ans[i]:newp) ;
            }
        }
        cout << ans[n] << endl ;
        for(int i=0 ; i<=n ; ++i) top[i]=0 ;
    }
    return 0 ;
}