#include<cstring>//memset头文件 
#include<algorithm>//fill头文件 
#include<vector>
#include<stdio.h>
#include<stack>
#include<queue> 
using namespace std;
const int MAXV=510;
struct Node{
	int v,w;
	Node(int _v,int _w):v(_v),w(_w) {}
};
vector<Node> G[MAXV];
int ve[MAXV],vl[MAXV];//事件最早发生时间、最迟发生时间 
int inDegree[MAXV];//入度 
int n,m;

stack<int> topOrder;//拓扑序列 
//拓扑排序，求ve 
bool topological(){
	queue<int> q;
	for(int i=0;i<n;i++){//初始化 
		if(inDegree[i]==0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		topOrder.push(u);//将u加入拓扑序列 
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].v;
			inDegree[v]--;
			if(inDegree[v]==0){
				q.push(v);
			}
			if(ve[u]+G[u][i].w>ve[v]){  //用ve[u]更新ve[v] 
				ve[v]=ve[u]+G[u][i].w;
			}
		}
	}
	if(topOrder.size()==n) return true;
	else return false;
}
//关键路径 
int CriticalPath(){
	memset(ve,0,sizeof(ve));
	if(topological()==false){//有环 
		return -1;
	}
	fill(vl,vl+n,ve[n-1]);
	//出栈即逆拓扑排序，求vl 
	while(!topOrder.empty()){
		int u=topOrder.top();
		topOrder.pop();
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].v;
			if(vl[v]-G[u][i].w<vl[u]){ //用vl[v]更新vl[u] 
				vl[u]=vl[v]-G[u][i].w;
			}
		} 
	}
	//遍历所有边，计算活动的最早开始时间和最迟开始时间
	for(int u=0;u<n;u++){
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].v,w=G[u][i].w;
			int e=ve[u],l=vl[v]-w;
			if(e==l) printf("%d->%d\n",u,v);//关键活动 
		}
	}
	return ve[n-1];//关键路径长度 
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%d",&inDegree[i]);
	}
	int u,v,w;
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&u,&v,&w);
		G[u].push_back(Node(v,w));			
	}
	printf("关键路径长度：%d",CriticalPath());
	return 0;
}