view code//首先为除根之外的每个点选定一条入边，这条入边一定要是所有入边中最小的。//现在所有的最小 入边都选择出来了，如果这个入边集不存在有向环的话，我们//可以证明这个集合就是该图的最小树形图。这个证明并不是很难。如果存在有向//环的话，我们就要将这 个有向环所称一个人工顶点，同时改变图中边的权。假//设某点u在该环上，并设这个环中指向u的边权是in[u]，那么对于每条从u出发的//边(u, i, w)，在新图中连接(new, i, w)的边，其中new为新加的人工顶点; 对//于每条进入u的边(i, u, w)，在新图中建立边(i, new, w-in[u])的边。为什么//入边的权要减去in[u]，这个后面会解释，在这里先给出算法的步骤。然后可以//证明，新图中最小树形图的权加上旧图中被收缩 的那个环的权和，就是原图中//最小树形图的权。#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;typedef long long ll;const int INF = 1<<30;const int N = 600;const int M = N*N;int n, m, lev[55], pre[N], begid[N];int s, t, in[N<<1], p[N], vis[N], id[N];struct edge{    int u, v, w;    edge() {}    edge(int u, int v, int w):u(u),v(v),w(w) {}}e[M];int ecnt;inline void addedge(int u, int v, int w){    e[ecnt++] = edge(u, v, w);}int DirMst(int rt, int num)//根结点，结点数目{    int ans = 0;    while(1)    {        for(int i=0; i<num; i++) in[i] = INF;        for(int i=0; i<ecnt; i++)        {            int u = e[i].u, v = e[i].v;            if(in[v]>e[i].w && u!=v)            {                in[v] = e[i].w;                pre[v] = u;            }        }        for(int i=0; i<num; i++) if(i!=rt && in[i]==INF) return -1;        int cnt = 0;        memset(id, -1, sizeof(id));        memset(vis, -1, sizeof(vis));        in[rt] = 0;        for(int i=0; i<num; i++)        {            ans += in[i];            int v = i;            while(vis[v]!=i && v!=rt && id[v]==-1)// 找环            {                vis[v] = i;                v = pre[v];            }            while(v!=rt && id[v]==-1)// 有环，重新编号            {                int u = pre[v];                for(;u!=v; u=pre[u]) id[u]=cnt;                id[v] = cnt++;            }        }        if(cnt==0) break;        for(int i=0; i<num; i++) if(id[i]==-1) id[i]=cnt++;// 不在环内，重新编号        for(int i=0; i<ecnt; i++)// 更新环外点和环缩点后的点的距离        {            int u = e[i].u, v = e[i].v;            e[i].u = id[u];            e[i].v = id[v];            if(id[u]!=id[v]) e[i].w -= in[v];        }        num = cnt;        rt = id[rt];    }    return ans;}void solve(){    ecnt = 0;    for(int i=1; i<=n; i++) scanf("%d", lev+i);    for(int i=1; i<=n; i++) begid[i] = begid[i-1]+lev[i-1]+1;    s = 0, t = begid[n]+lev[n]+1;    for(int i=1; i<=n; i++)    {        addedge(s, begid[i], 0);        for(int j=0; j<lev[i]; j++)        {            addedge(begid[i]+j+1, begid[i]+j, 0);        }    }    int c, l, d, r, w;    for(int i=0; i<m; i++)    {        scanf("%d%d%d%d%d", &c, &l, &d, &r, &w);        int u = begid[c]+l ,v = begid[d]+r;        addedge(u, v, w);    }    printf("%d\n", DirMst(s, t));}int main(){//    freopen("in.txt", "r", stdin);    while(scanf("%d%d", &n, &m)>0 && (n|m)) solve();    return 0;}