//  Solutie:
//    
//    b - numarul membrilor organizatiei; b<=50.
//    m - numarul drumurilor intre orase (muchiilor); m<=300
//    n - numarul oraselor (arcelor); n<=50.
//    
//    T unitati de timp sunt suficiente, daca fluxul maxim in reteaua de transport
//       ((v,t),(w,t+1)) pentru 0<=t<T unde {v,w} este muchie in graful oraselor,
//       ((v,t),(v,t+1)) pentru 0<=t<T unde v este oras,
//       ((0,0), (v,0))  unde v este un oras
//       ((v,T), (0,T)) unde v este un oras
//       s = (0,0), t = (0,T+1)
//    este egal cu numarul membrilor organizatiei.
//    
//    Fluxul maxim este cel mult egal cu b.
//    m' - numarul de arce ale retelei reziduale.
//    Cu BFS, un drum de la s la t se gaseste in cel mult m' operatii.
//    Fluxul maxim se poate calcula cu ford-fulkerson, in cel mult b*m' operatii.
//    
//    Topt <= Tmax=((n-1)+(b-1)) :
//       {1,2},{2,3},...,{n-1,n}, pe fiecare din aceste muchii trece maxim 1 om, b oameni in n.
//    
//    Topt se cauta binar in multimea {1,...,Tmax}.

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

int const maxn = 50;
int const maxm = 300;
int const maxc = 50;
int const minl = 1;
int const maxl = 10;

typedef std::pair<int, int> cendp_t; // - edge with its capacity

struct flow_network             // - a flow network with a feasible flow
{ int a_source;
  int a_sink;
  std::vector<std::vector<cendp_t> > a_adj; // - arcs with their capacities
};

int
max_flow(flow_network & fnet)
{ // The input of this routine is fnet.
  // fnet represents a flow network
  // with a initial feasible flow.
  // The output of this routine is
  // the value of a maximum flow for fnet.
  std::vector<std::vector<cendp_t > > & adj (fnet.a_adj);
  int source; source = fnet.a_source;
  int sink; sink = fnet.a_sink;
  // Start with initial zero flow.
  int n; n = static_cast<int> (adj.size());
  std::vector<std::vector<int> > flow(n);
  int x;
  for(x=0; n>x; ++x)
  { std::vector<int> r0(n, 0); // - row with zeroes
    flow[x].swap(r0);
  }
  // Augument paths with edmonds - karp algorithm.
  // The Edmonds - karp algorithm is a ford-fulkerson algorithm.
  int flow_value; flow_value = 0;
  int len; int i; int y; int cxy; int new_flow;
  do
  { std::queue<int> bfs_queue; bfs_queue.push(source);
    std::vector<int> bfs_parent(n, -1); bfs_parent[source] = -2;
    std::vector<int> fxy(n, -1);
    while(!bfs_queue.empty())
    { x = bfs_queue.front(); bfs_queue.pop();
      len = static_cast<int>(adj[x].size());
      for(i=0; len>i; ++i)
      { y = adj[x][i].first; cxy = adj[x][i].second;
        if((-1 == bfs_parent[y])&&(flow[x][y]<cxy))
        { bfs_parent[y] = x; fxy[y] = cxy - flow[x][y]; bfs_queue.push(y); }
      }
    }
    if(-1!=bfs_parent[sink])
    { new_flow = -1;
      for(y=sink; source != y; y = bfs_parent[y])
      { if((-1==new_flow)||(new_flow>fxy[y])) { new_flow = fxy[y]; } }
      for(y=sink; source != y; y = x)
      { x = bfs_parent[y]; flow[x][y] += new_flow; flow[y][x] -= new_flow; }
      flow_value += new_flow;
    }
    else { new_flow = 0; }
  }
  while(0<new_flow);
  return flow_value;
}

class algola
{ std::vector<int>   a_b;
  std::vector<std::vector<cendp_t> > a_adj;
  int a_c;
  int a_ans;
  bool a_ok;
  // helper (2) methods
  void construct_flow_network(int tmax, flow_network & fnet);
  // helper methods
  bool write();
  void solve();
  bool read();
  bool process();
  public:
  algola();
  bool get_ok() const throw();
};

algola::algola()
: a_ok(process())
{
}

bool
algola::get_ok() const throw()
{ return a_ok; }

bool
algola::process()
{ bool ok; ok = read();  if(!ok) { return ok; }
  solve(); ok = write(); return ok;
}

bool
algola::read()
{ // read input
  bool ok;
  std::ifstream is("algola.in");
  ok = is.good(); if(!ok) { return ok; }
  int n; int m; is >> n >> m;
  ok = ((0<n)&&(maxn>=n)); if(!ok) { return ok; }
  ok = ((0<m)&&(maxm>=m)); if(!ok) { return ok; }
  std::vector<int> b(1+n);
  int x; for(x=1; n>=x; ++x)
  { is >> b[x];
    ok = (0<=b[x]); if(!ok) { return ok; }
  }
  int c; c = 0; for(x=1; n>=x; ++x) { c += b[x]; }
  ok = ((1<=c)&&(c<=maxc)); if(!ok) { return ok; }
  std::vector<std::vector<cendp_t> > adj(1+n);
  int i; int y; int l;
  for(i=0; m>i; ++i)
  { is >> x >> y >> l;
    ok = ((1<=x)&&(x<=n)); if(!ok) { return ok; }
    ok = ((1<=y)&&(y<=n)); if(!ok) { return ok; }
    ok = ((minl<=l)&&(l<=maxl)); if(!ok) { return ok; }
    adj[x].push_back(cendp_t(y, l));
    adj[y].push_back(cendp_t(x, l));
  }
  ok = is.good(); if(!ok) { return ok; }
  // no-throw
  b.swap(a_b);
  adj.swap(a_adj);
  a_c = c;
  return ok;
}

void
algola::solve()
{ // solve
  int n; n = static_cast<int>(a_b.size()) - 1;
  // ( - cast is guaranteed to work: solve() is
  //     only called if read() call returned true,
  //     read() returns true only if b.size() <= maxn+1,
  //     maxn == 50, and 50 surely fits an int.
  // )
  int c; c = a_c;
  int t1(0); int t3((n-1)+(c-1));
  int t2; int flow; int anse;
  while(t1<=t3)
  { t2 = ((t1+t3)/2);
    // construct transport network with sink (1,tmax)
    flow_network fnet;
    construct_flow_network(t2, fnet);
    // compute max-flow
    flow = max_flow(fnet);
    // update answer estimate, search interval
    if(c==flow)
    { anse = t2; t3 = t2-1; }
    else
    { t1 = t2+1; }
  }
  // no-throw
  a_ans = anse;
}

bool
algola::write()
{ // write solution
  std::ofstream os("algola.out");
  os << a_ans << std::endl;
  bool ok = os.good(); if(!ok) { return ok; }
  os.close(); ok = os.good(); if(!ok) { return ok; }
  return ok;
}

void
algola::construct_flow_network(int tmax, flow_network & fnet)
{ // network flow with nodes (x,t)
  // with x=0,1,2,...,n, and t=0,1,...,tmax
  // (x,t) <- bijection -> t*(n+1)+x
  std::vector<int> & b (a_b);
  int n; n = static_cast<int>(b.size());
  // ( - the value in variable n is '1+n' ) 
  int tn = (1+tmax) * n; int x;
  std::vector<std::vector<cendp_t> > & adj (a_adj);
  std::vector<std::vector<cendp_t> > ac(tn); // - arcs with their capacities
  for(x=1; n>x; ++x)
  { if(0<b[x])
    { ac[0*n+0].push_back(cendp_t(0*n+x, b[x]));
      ac[0*n+x].push_back(cendp_t(0*n+0, 0));
    }
  }
  int c; c = a_c;
  int t1; int t2; int dx; int i; int y; int l;
  for(x=1; n>x; ++x)
  { for(t1=0; tmax>t1; ++t1)
    { t2 = t1+1;
      ac[t1*n+x].push_back(cendp_t(t2*n+x, c));
      ac[t2*n+x].push_back(cendp_t(t1*n+x, 0));
      dx = static_cast<int> (adj[x].size()); // degree of x
      // ( - cast is ok because adj[x].size() <= m, m<=maxm, maxm==300,
      //     and int is able to represent 300. )
      for(i=0; dx>i; ++i)
      { y = adj[x][i].first; l = adj[x][i].second;
        ac[t1*n+x].push_back(cendp_t(t2*n+y, l));
        ac[t2*n+y].push_back(cendp_t(t1*n+x, 0));
      }
    }
  }
  // no-throw
  fnet.a_source = 0*n + 0;
  fnet.a_sink   = tmax*n + 1;
  fnet.a_adj.swap(ac);
}

bool
solve()
{ algola a;
  return a.get_ok();
}

int
main()
{ int status;
  bool ok;
  try
  { ok = solve();
    status = ( ok ? 0 : 1 );
  }
  catch ( ... )
  { status = 2; }
  return status;
}