1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 #define MaxSize 50005
 5 #define inf 0x7ffffff
 6 struct  edge{
 7     int a,b,c;
 8 }eg[MaxSize];
 9 int n;
10 int d[MaxSize];
11 void bellman_Ford(int s,int e){
12     int i,j;
13     for(i=s;i<=e;i++)
14         d[i]=0;
15     //d[b]-d[a],由于b增加1過，因此，相當于d[a]為d[a-1],d[b]-d[a]的意義為[a,b]區間內符合條件的元素
16     for(i=s+1;i<e;i++){
17         bool flag=true;
18         for(j=0;j<n;j++)//約束條件，[a,b]區間內元素不少于c,即d[b]-d[a]>=c
19             if(d[eg[j].b]-eg[j].c<d[eg[j].a] )
20                 d[eg[j].a]=d[eg[j].b]-eg[j].c,flag=false;
21         for(j=e;j>s;j--)
22             if(d[j]<d[j-1])//約束條件,[m,m+1],d[m]<=d[m+1]
23                 d[j-1]=d[j],flag=false;
24         for(j=s+1;j<=e;j++)
25             if(d[j-1]+1<d[j])//d[m]+1>=d[m+1];
26                 d[j]=d[j-1]+1,flag=false;
27         if(flag)
28             return;
29     }
30 }
31 int main(){
32     freopen("in.txt","r",stdin);
33     while (~scanf("%d",&n)){
34         int i,s,e;
35         s=inf;
36         e=-inf;
37         for(i=0;i<n;i++){
38             scanf("%d %d %d",&eg[i].a,&eg[i].b,&eg[i].c);
39             eg[i].b++;//考慮到可能在計算會用到a-1，而當a=0時就越界了，因此整體加一
40             if(eg[i].a<s)
41                 s=eg[i].a;
42             if(eg[i].b>e)
43                 e=eg[i].b;
44         }
45         bellman_Ford(s,e);
46         printf("%d\n",d[e]-d[s]);
47     }
48     return 0;
49 }