#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>

#define ll long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mp(a, b) make_pair(a, b)


using namespace std;

#define cin in
#define cout out

ifstream in("dwarf.in");
ofstream out("dwarf.out");

ll a[1234567];

struct p
{
    ll x, a, b, c;
    p(ll xx, ll aa, ll bb, ll cc)
    {
        x = xx;
        a = aa;
        b = bb;
        c = cc;
    }
};


bool operator<(p aa, p bb)
{
    return (a[aa.a] + a[aa.b] + 1)*9999999ll + aa.c < (a[bb.a] + a[bb.b] + 1)*9999999ll + bb.c;
}

vector<vector<p> > vc;

int main()
{
    set<p> st;
    int n, m;
    cin >> n >> m;
    vc.resize(n+1);
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    p t(0,0,0,0);
    for(int i = 0 ; i < m; ++i)
    {
        cin >> t.x >> t.a >> t.b;
        t.c = i + 1;
        st.insert(t);
        vc[t.a].push_back(t);
        vc[t.b].push_back(t);
    }

    while(st.size())
    {
        p pp = *(st.begin());
        st.erase(pp);
        if(a[pp.a] + a[pp.b] < a[pp.x])
        {
            a[pp.x] = a[pp.a] + a[pp.b];
            if(pp.x == 1)
            {
                cout << a[1];
                return 0;
            }
            for(unsigned int j = 0; j < vc[pp.x].size(); ++j)
                if(a[vc[pp.x][j].a] + a[vc[pp.x][j].b] < a[vc[pp.x][j].x])
                    if(st.find(vc[pp.x][j]) != st.end())
                    {
                        st.erase(vc[pp.x][j]);
                        st.insert(vc[pp.x][j]);
                    }
        }

    }
    cout << a[1];
    return 0;

}