/**POJ 1201 Intervals*差分约束系统*见《图论算法理论、实现及应用》 P205*设s[i] 是集合Z中小于等于i的元素的个数，即s[i] = |{s|s∈Z, s<=i}|*则有以下不等式组：*	(1)Z集合中范围在[ai, bi] 的整数的个数即s[bi] - s[ai-1] >= ci, 得到约束条件(1):*		s[a(i-1)] - s[bi] <= -ci*	根据实际情况还有:*	(2) s[i] - s[i-1] <= 1*	(3) s[i] - s[i-1] >= 0 即 s[i-1] - s[i] <= 0**设所有区间右端点的最大值为maxright, 左端点最小值为minlift*最终要求的是s[maxright] - s[minlift-1]的最小值*即 s[minlift-1] - s[maxright] <= -M*即 dist[maxright] - dist[minlift-1]*//**优化:*	先只用约束条件(1) 建网， 各顶点到源点的初始距离为 0，本题源点为s[maxright]*	bellman 求解：*		加入条件(2) 进行判断*		加入条件(3) 进行判断*	且 一次while循环后没有距离的变化，可以提前结束bellman*/#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MAXN = 50002;const int INF = 0x3f3f3f3f;struct Edge {	int u, v, w;} edges[MAXN];int dist[MAXN];int n;int minlift;int maxright;void init(){	int i;	for (i = 0; i < MAXN; i++) {		dist[i] = 0;	}	minlift = INF;	maxright = 1;}bool bellman_ford(){	int i, temp;	int flag = 1;	while (flag) {		flag = 0;		/*约束条件：s[ai-1] - s[bi] <= -c*/		for (i = 0; i < n; i++) {			temp = dist[edges[i].u] + edges[i].w;			if (dist[edges[i].v] > temp) {				dist[edges[i].v] = temp;				flag = 1;			}		}		/*约束条件： s[i] - s[i-1] <= 1*/		for (i = minlift; i <= maxright; i++) {			temp = dist[i - 1] + 1;			if (dist[i] > temp) {				dist[i] = temp;				flag = 1;			}		}		/*约束条件： s[i-1] - s[i] <= 0*/		for (i = maxright; i >= minlift; i--) {			if (dist[i - 1] > dist[i]) {				dist[i - 1] = dist[i];				flag = 1;			}		}	}	return true;}int main(){	while (~scanf("%d", &n)) {		init();		int i;		int u, v, w;		for (i = 0; i < n; i++) {			scanf("%d %d %d", &u, &v, &w);			edges[i].u = v; edges[i].v = u - 1;   edges[i].w = -w;			minlift = min(minlift, u);			maxright = max(maxright, v);		}		bellman_ford();		printf("%d\n", dist[maxright] - dist[minlift - 1]);	}	return 0;}