/*
ID: espr1t
TASK: Lovers
KEYWORDS: Medium, Dijkstra
*/

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
FILE* in = stdin; FILE* out = stdout;

const int MAX = 10004;

struct Edge {
	int to, price;
	Edge(int to_ = 0, int price_ = 0) : to(to_), price(price_) {}
};

struct State {
	int node, last, time;

	bool operator < (const State& r) const {
		if (time != r.time) return time > r.time;
		if (node != r.node) return node > r.node;
		return last < r.last;
	}
};

int n, m;
int wait[MAX];
vector <Edge> v[MAX];

priority_queue <State> q;
int dist[MAX], last[MAX];

void dijkstra(int origin, int destination) {
	State cur, nxt;
	memset(last, -1, sizeof(last));
	memset(dist, 63, sizeof(dist));
	while (!q.empty()) q.pop();

	nxt.node = origin; nxt.time = 0; nxt.last = -1;
	dist[nxt.node] = 0;
	q.push(nxt);

	while (!q.empty()) {
		cur = q.top(); q.pop();
		if (dist[cur.node] < cur.time)
           continue;
		last[cur.node] = cur.last;
		dist[cur.node] = -1;
		if (cur.node == destination) break;

		if (cur.time % wait[cur.node])
			cur.time += wait[cur.node] - cur.time % wait[cur.node];

		for (int i = 0; i < (int)v[cur.node].size(); i++) {
			nxt.last = cur.node;
			nxt.node = v[cur.node][i].to;
			nxt.time = v[cur.node][i].price + cur.time;

			if (dist[nxt.node] > nxt.time) {
			    dist[nxt.node] = nxt.time;
			    q.push(nxt);
            }
		}
	}

	if (cur.node != destination) {
       fprintf(out, "-1\n");
    }
    else {
		vector <int> path;
		while (cur.node != -1)
			path.push_back(cur.node), cur.node = last[cur.node];
		reverse(path.begin(), path.end());

		fprintf(out, "%d\n", cur.time);
		fprintf(out, "%d\n", (int)path.size());
		for (int i = 0; i < (int)path.size(); i++)
			fprintf(out, "%d%c", path[i], i + 1 == (int)path.size() ? '\n' : ' ');
	}
}

int main(void) {
//	in = fopen("Lovers.in", "rt"); out = fopen("Lovers.out", "wt");

	fscanf(in, "%d %d", &n, &m);
	for (int i = 0; i < n; i++)
        fscanf(in, "%d", &wait[i]);
	for (int i = 0; i < m; i++) {
		int from, to, price;
		fscanf(in, "%d %d %d", &from, &to, &price);
		v[from].push_back(Edge(to, price));
	}
	dijkstra(0, n - 1);
	return 0;
}