#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;
typedef long long ll;

struct E {
	int dst; ll cost;
	E(int ldst, ll lcost) {
		dst = ldst; cost = lcost;
	}
};

int main() {
	int ncase; cin >> ncase;
	for (int csnum = 1; csnum <= ncase; csnum++) {
		int nv, ne; cin >> nv >> ne;
		vector<E> adj[nv*2];
		int indegree[nv*2];
		memset(indegree, 0, sizeof indegree);
		for (int i = 0; i < nv; i++) {
			int profit; cin >> profit;
			adj[i].push_back(E(nv+i, -profit));
			indegree[nv+i]++;
		}
		for (int i = 0; i < ne; i++) {
			int a, b, cost; cin >> a >> b >> cost;
			a--; b--;
			adj[nv+a].push_back(E(b, cost));
			indegree[b]++;
		}
		// toposort
		queue<int> q;
		int ind = 0;
		int sorted[nv*2];
		for (int i = 0; i < nv*2; i++) {
			if (indegree[i] == 0) {
				q.push(i);
			}
		}
		while (!q.empty()) {
			int curr = q.front();
			q.pop();
			sorted[ind] = curr;
			ind++;
			for (int i = 0; i < adj[curr].size(); i++) {
				int j = adj[curr][i].dst;
				indegree[j]--;
				if (indegree[j] == 0) {
					q.push(j);
				}
			}
		}
		ll dp[nv*2];
		int parent[nv*2];
		memset(dp, 0x3f, sizeof dp);
		memset(parent, -1, sizeof parent);
		dp[0] = 0;
		for (int i = 0; i < nv*2; i++) {
			int ii = sorted[i];
			for (int j = 0; j < adj[ii].size(); j++) {
				int dst = adj[ii][j].dst;
				ll cost2 = dp[ii] + adj[ii][j].cost;
				if (cost2 < dp[dst]) {
					dp[dst] = cost2;
					parent[dst] = ii;
				}
			}
		}
		int bestind = 0;
		ll bestcost = dp[0];
		for (int i = 1; i < nv*2; i++) {
			if (dp[i] < bestcost) {
				bestcost = dp[i];
				bestind = i;
			}
		}
		vector<int> blah;
		int curr = bestind;
		while (parent[curr] >= 0) {
			blah.push_back(curr);
			curr = parent[curr];
		}
		cout << -bestcost << " " << blah.size()/2+1 << endl;
		cout << 1;
		for (int i = (int)blah.size() - 2; i >= 0; i-=2) {
			cout << " " << blah[i] + 1;
		}
		cout << endl;
	}
}