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

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

#define MAX 16384
using namespace std;
FILE *in; FILE *out;

struct Child
{
	int node, time;
	Child(int node_ = 0, int time_ = 0) {node = node_; time = time_;}
};

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 <Child> v[MAX];

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


void dijkstra(int start, int end)
{
	State cur, next;
	memset(vis, 0, sizeof(vis));
	memset(last, -1, sizeof(last));
	while (!q.empty()) q.pop();
	
	next.node = start; next.time = 0; next.last = -1;
	q.push(next);
	
	while (!q.empty())
	{
		cur = q.top(); q.pop();
		
		if (vis[cur.node]) continue;
		vis[cur.node] = 1; last[cur.node] = cur.last;
		if (cur.node == end) 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++)
		{
			next.last = cur.node;
			next.node = v[cur.node][i].node;
			next.time = v[cur.node][i].time + cur.time;
			
			if (!vis[next.node]) q.push(next);
		}
	}
	
	if (cur.node != end) 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 = stdin; out = stdout;
//	in = fopen("Lovers.in", "rt"); out = fopen("Lovers.sol", "wt");
	
	int numTests = 1;
//	fscanf(in, "%d", &numTests);
	
	for (int test = 0; test < numTests; test++)
	{
		fscanf(in, "%d %d", &n, &m);
		for (int i=0; i<MAX; i++) v[i].clear();

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