#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define FastIO ios::sync_with_stdio(false)
#define read freopen("in.in","r",stdin)
#define write freopen("out.out","w",stdout)
typedef long long ll;
const int N = 2e5 + 5;
const int MOD = 1e9 + 7;
typedef pair<ll, ll> ii;
typedef long long ll;
double ebs = 1e-9;
vector<vector<pair<int, char>>>adjlist;
int vis[N], level[N], parent[N];
string lex[N];
struct Compare {
	bool operator()(pair<string, int> const& p1, pair<string, int> const& p2)
	{
		if (p1.first.length() == p2.first.length())
			return p1.first > p2.first;
		return p1.first.length() > p2.first.length();
	}
};
void bfs(int source, int dis) {
	vis[source] = 1;
	level[source] = 0;
	lex[source] = "";
	priority_queue< pair<string, int>, vector<pair<string, int>>, Compare>q;
	q.push(make_pair("", source));
	while (!q.empty()) {
		int node = q.top().second;
		q.pop();

		if (node == dis)break;
		for (int i = 0; i < adjlist[node].size(); i++)
		{
			int child = adjlist[node][i].first;
			if (!vis[child]) {
				parent[child] = node;
				level[child] = level[node] + 1;
				lex[child] = lex[node] + adjlist[node][i].second;
				vis[child] = 1;
				q.push(make_pair(lex[child], child));
			}
		}
	}
}
void print(int dis) {
	vector<int>res;
	int node = dis;
	while (node != -1) {
		res.push_back(node);
		node = parent[node];
	}
	if (res[0] == dis && res[res.size() - 1] == 1) {
		for (int i = res.size() - 1; i >= 0; i--)
			cout << res[i] << " ";
		cout << endl;
	}
	else
		cout << -1 << endl;
}
int main() {
	FastIO;
#ifndef ONLINE_JUDGE
	write; read;
#endif 
	int n, m; cin >> n >> m;
	adjlist.resize(n + 1);
	memset(parent, -1, sizeof parent);
	memset(vis, 0, sizeof vis);
	memset(level, 0, sizeof level);
	for (int i = 0; i < n; i++)
		lex[i] = "";
	int a, b;
	char c;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		adjlist[a].push_back({ b,c });
		adjlist[b].push_back({ a,c });
	}
	bfs(1, n);
	cout << level[n] << endl;
	print(n);
	cout << lex[n] << endl;

}