#t = int(input())
tt = 1
import random
R = random.randint(1, 1 << 60)
from collections import deque
from heapq import heappush, heappop

INF = 10**30
def Johnson(G, N):
    h = [0]*N

    update = 1
    for i in range(N):
        update = 0
        for v in range(N):
            d = h[v]
            for w, c in G[v]:
                if c + d < h[w]:
                    h[w] = d + c
                    update = 1
        if not update:
            break
    else:
        return None

    for v in range(N):
        d = h[v]
        g = G[v]
        for j, (w, c) in enumerate(g):
            g[j] = (w, c + d - h[w])

    D = []
    for i in range(N):
        dst = [INF]*N
        dst[i] = 0
        que = [(0, i)]
        while que:
            cost, v = heappop(que)
            if dst[v] < cost:
                continue
            for w, c in G[v]:
                if cost + c < dst[w]:
                    dst[w] = r = cost + c
                    heappush(que, (r, w))
        v = h[i]
        for j in range(N):
            if dst[j] == INF:
                dst[j] = INF
            else:
                dst[j] -= v - h[j]
        D.append(dst)

    return D
for _ in range(tt):
  n,m = map(int, input().split())
  p = list(map(int, input().split()))
  edge = [[] for _ in range(n)]
  for i in range(m):
    u,v,t = map(int, input().split())
    u -= 1
    v -= 1
    edge[u].append([v,t])
  dis = Johnson(edge,n)
  mi = 10**30
  ko = 0
  for i in range(n):
    for j in range(i+1,n):
      cur = dis[i][j]+p[i]+p[j]
      if cur == mi:
        ko += 1
      elif cur < mi:
        mi = cur
        ko = 1
  if mi == 10**30:
    print(-1)
  else:
    print(mi,ko)