#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define NUM 105
#define DIFF 40000

typedef pair<int,int> P;


struct Info{
	Info(int arg_node_id,int arg_sum_stage){
		node_id = arg_node_id;
		sum_stage = arg_sum_stage;
	}
	int node_id,sum_stage;
};

struct Data{
	Data(int arg_to,int arg_value){
		to = arg_to;
		value = arg_value;
	}
	int to,value;
};


struct Edge{
	Edge(int arg_to,int arg_capacity,int arg_cost,int arg_rev_index){
		to = arg_to;
		capacity = arg_capacity;
		cost = arg_cost;
		rev_index = arg_rev_index;
	}

	int to,capacity,cost,rev_index;
};

int V,E;
vector<Data> first_G[NUM];
vector<Edge> G[NUM];
int h[NUM];
int dist[NUM];
int pre_node[NUM],pre_edge[NUM];
int start,goal;
int in_num[NUM],max_stage[NUM];



void add_edge(int from,int to,int capacity,int cost){
	G[from].push_back(Edge(to,capacity,cost,G[to].size()));
	G[to].push_back(Edge(from,0,-cost,G[from].size()-1));
}


int min_cost_flow(int source,int sink,int flow){
	int ret = 0;
	for(int i = 0; i < V; i++)h[i] = 0;
	while(flow > 0){

		priority_queue<P,vector<P>,greater<P>> Q;
		for(int i = 0; i < V; i++)dist[i] = BIG_NUM;
		dist[source] = 0;
		Q.push(P(0,source));

		while(!Q.empty()){
			P p = Q.top();
			Q.pop();
			int node_id = p.second;
			if(dist[node_id] < p.first)continue;
			for(int i = 0; i < G[node_id].size(); i++){
				Edge &e = G[node_id][i];
				if(e.capacity > 0 && dist[e.to] > dist[node_id]+e.cost+h[node_id]-h[e.to]){
					dist[e.to] = dist[node_id]+e.cost+h[node_id]-h[e.to];
					pre_node[e.to] = node_id;
					pre_edge[e.to] = i;
					Q.push(P(dist[e.to],e.to));
				}
			}
		}

		if(dist[sink] == BIG_NUM){
			return -1;
		}

		for(int node_id = 0; node_id < V; node_id++)h[node_id] += dist[node_id];

		int tmp_flow = flow;
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			tmp_flow = min(tmp_flow,G[pre_node[node_id]][pre_edge[node_id]].capacity);
		}
		flow -= tmp_flow;
		ret += tmp_flow*h[sink];
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			Edge &e = G[pre_node[node_id]][pre_edge[node_id]];
			e.capacity -= tmp_flow;
			G[node_id][e.rev_index].capacity += tmp_flow;
		}
	}
	return ret;
}

int main(){

	scanf("%d %d",&V,&E);

	start = 0;
	goal = V-1;

	for(int i = 0; i < V; i++){

		in_num[i] = 0;
		max_stage[i] = 0;
	}

	int from,to,capacity,cost;

	capacity = 1000000;

	for(int loop = 0; loop < E; loop++){

		scanf("%d %d %d",&from,&to,&cost);
		first_G[from].push_back(Data(to,cost));

		in_num[to]++;
	}

	queue<Info> Q;

	for(int i = 0; i < V; i++){

		if(in_num[i] == 0){
			Q.push(Info(i,0));
		}
	}

	while(!Q.empty()){

		for(int i = 0; i < first_G[Q.front().node_id].size(); i++){

			int next_node = first_G[Q.front().node_id][i].to;
			int next_sum_stage = Q.front().sum_stage+first_G[Q.front().node_id][i].value;

			max_stage[next_node] = max(max_stage[next_node],next_sum_stage);

			in_num[next_node]--;

			if(in_num[next_node] == 0){

				Q.push(Info(next_node,max_stage[next_node]));
			}
		}
		Q.pop();
	}

	int maximum = max_stage[goal];

	int sink = V;
	V++;

	add_edge(goal,sink,capacity,maximum);

	for(int i = 0; i <= goal; i++){

		for(int k = 0; k < first_G[i].size(); k++){

			add_edge(i,first_G[i][k].to,capacity,-first_G[i][k].value);
			add_edge(i,first_G[i][k].to,1,-first_G[i][k].value-DIFF);
		}
	}

	printf("%d\n",min_cost_flow(start,sink,DIFF)+E*DIFF);

	return 0;
}




Measured memory_bytes: 3300