1463
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <math.h>
#include <limits.h>
 
using namespace std;
 
// Datatypes
typedef vector<int> vi; 
typedef vector<string> vs;
typedef vector<vi> vvi; 
typedef pair<int,int> ii; 
typedef long long ll;
typedef long double ld;
 
// Define
#define sz(a)             int((a).size()) 
#define pb                push_back 
#define all(c)            (c).begin(),(c).end() 
#define present(c,x)      ((c).find(x) != (c).end()) 
#define cpresent(c,x)     (find(all(c),x) != (c).end()) 
#define FOR(_i,_n)        for(int (_i) = 0; (_i) < (_n); (_i)++)
#define MP make_pair
 
// Constants
const double eps = 1e-8; 
const double PI = 3.1415926535897932384626433832795;
 
#define INPUT_FILE "xo.in"
#define OUTPUT_FILE "xo.out"
 
int diam = 0;
int diamv;
vector< vector< pair<int,int> > > E;
vector< int > color;
vector< int > C;
vector< int > m1v;
vector< int > m2v;
list<int> L;
 
int dfs(int v)
{
    color[v] = 1;
 
    if(E[v].size() == 0)
    {
        if(C[v] > diam)
        {
            diamv = v;
            diam = C[v];
        }
 
        return C[v];
    } else {
        int m1 = 0;
        int _m1v;
        int m2 = 0;
        int _m2v;
        int c = 0;
 
        for(int i = 0; i < E[v].size(); i++)
        {
            int u = E[v][i].first;
 
            if(color[u] == 0)
            {
                c++;
                int cc = E[v][i].second;
                int m = dfs(u) + cc;
 
                if(m > m1)
                {
                    m2v[v] = m1v[v];
                    m1v[v] = u;
                    m2 = m1;
                    m1 = m;
                }
                else if (m > m2)
                {
                    m2v[v] = u;
                    m2 = m;
                }
            }
        }
 
        if(c > 1)
        {
            if(m1 + m2 + C[v] > diam)
            {
                diamv = v;
                diam = m1 + m2 + C[v];
            }
        }
 
        if(m1 + C[v] > diam)
        {
            diamv = v;
            diam = m1 + C[v];
        }
 
        return m1 + C[v];
    }
}
 
void pr(int v)
{
    while(v != 0)
    {
        L.pb(v);
        v = m1v[v];
    }
}
 
void pr2(int v)
{
    while(v != 0)
    {
        L.push_front(v);
        v = m1v[v];
    }
}
 
int main(void)
{
#ifndef ALEX
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
    //freopen(INPUT_FILE, "r", stdin);
    //freopen(OUTPUT_FILE, "w", stdout);
#endif
 
    int N,K;
 
    cin >> N >> K;
 
    C.resize(N+1);
    color.resize(N+1);
    E.resize(N+1);
    m1v.resize(N+1);
    m2v.resize(N+1);
 
    for(int i = 0; i < N; i++)
    {
        int t;
        scanf("%d", &t);
        C[i+1] = t;
    }
 
    for(int i = 0; i < K; i++)
    {
        int a,b,c;
 
        scanf("%d%d%d", &a, &b, &c);
 
        E[a].pb(MP(b,c));
        E[b].pb(MP(a,c));
    }
 
    for(int i = 1; i < N+1; i++)
    {
        if(color[i] == 0)
            dfs(i);
    }
 
    pr(diamv);
    pr2(m2v[diamv]);
 
    cout << diam << endl;
    cout << L.size() << endl;
 
    for(list<int>::iterator it = L.begin(); it != L.end(); it ++)
    {
        cout << *it << " ";
    }
 
    return 0;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.