Maximum Value Sum Path in a Weighted Graph

You are given an undirected weighted graph with n vertices and m edges. Each vertex is assigned an integer value. Your task is to find the maximum value sum over any simple path in the graph. A simple path is defined as a path that does not visit any vertex more than once.

The input consists of the number of vertices and edges, followed by a line of n integer vertex values, and then m lines describing the edges. Each edge is represented by three integers \(u\), \(w\), and \(l\) where \(u\) and \(w\) are the 1-indexed vertices it connects and \(l\) is the weight of the edge. Note: While the graph is weighted, the weight \(l\) is not used in calculating the path's value sum. The goal is solely to maximize the sum of the vertex values along a simple path.

Formula: For a simple path defined by vertices \(v_1, v_2, \ldots, v_k\), the value sum is given by:

\(S = \sum_{i=1}^{k} \text{value}(v_i)\)

Your solution should read the input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The first line contains two integers n and m representing the number of vertices and edges, respectively.

The second line contains n space-separated integers, where the i^th integer is the value of vertex i.

The next m lines each contain three integers \(u\), \(w\), and \(l\), which describe an edge between vertices \(u\) and \(w\) with weight \(l\).

outputFormat

Output a single integer, which is the maximum sum of vertex values on any simple path in the graph.

## sample

3 2
4 5 6
1 2 1
2 3 3

15