#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <fstream>
#include <chrono>
std::ifstream infile("TestInput.txt");
using namespace std;

const int N = 1e5;
double dis[N + 1];
int col[N + 1];
int previ[N + 1];
bool vis[N + 1] = { 0 };
vector<pair<int, double>> adj[N+1];

class cmp {
public:
	bool operator() (const pair<int, double> &p1, const pair<int, double> &p2) {
		return p1.second > p2.second;
	}
};

void dijkstra(int m) {
	for (int i = 0; i < m; i++) {
		dis[i] = INT_MAX;
		col[i] = INT_MAX;
		previ[i] = -1;
		vis[i] = false;
	}
	dis[1] = 0;
	priority_queue<pair<int, double>, vector<pair<int, double> >, cmp> q;
	q.push(make_pair(1, 0));
	while (!q.empty()) {
		pair<int, double> currPair = q.top();
		q.pop();
		int currVertex = currPair.first;
		double currWeight = currPair.second;

		if (vis[currVertex]) {
			continue;
		}
		if (currVertex == m-1) {
			break;
		}

		vis[currVertex] = true;
		for (int i = 0; i < adj[currVertex].size(); i++) {
			int nextVertex = adj[currVertex][i].first;
			int nextEdgeCol = adj[currVertex][i].second;
			int currEdgeCol = col[nextVertex];

			if (!vis[nextVertex]) {
				pair<int, int> newP;
				if (currWeight + 1 < dis[nextVertex]) {
					previ[nextVertex] = currVertex;
					dis[nextVertex] = currWeight + 1;
					col[nextVertex] = nextEdgeCol;
					newP = make_pair(nextVertex, dis[nextVertex]);
				} else if (currWeight + 1 == dis[nextVertex]) {
					if (col[nextVertex] > nextEdgeCol) {
						previ[nextVertex] = currVertex;
						dis[nextVertex] = currVertex + 1;
						col[nextVertex] = nextEdgeCol;
						newP = make_pair(nextVertex, dis[nextVertex]);
					}
				}
				q.push(newP);
			}
		}
	}
}

int main() {
	int n, m, v1, v2;
	double w;
	while (infile >> n >> m) {
		int k = 0;
		for (int i = 0; i < m; i++) {
			infile >> v1 >> v2 >> w;
			//TODO Only add smallest edge between 2 vertices
			adj[v1].push_back(make_pair(v2, w));
			adj[v2].push_back(make_pair(v1, w));
		}
		auto t1 = chrono::high_resolution_clock::now();
		dijkstra(n+1);
		auto t2 = chrono::high_resolution_clock::now();
		cout << "took "
			<< chrono::duration_cast<chrono::milliseconds>(t2 - t1).count()
			<< " millisecs "
			<< "\n";
		string outs;
		while (n != 1) {
			outs.insert(0, to_string(col[n]) + " ");
			n = previ[n];
			k++;
		}
		outs = outs.substr(0, outs.length()-1);
		cout << k << "\n";
		cout << outs << "\n";
		t1 = chrono::high_resolution_clock::now();
		for (auto& v : adj) {
			v.clear();
		}
		t2 = chrono::high_resolution_clock::now();
		cout << "Clearing adj took "
			 << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count()
			 << " millisecs "
			 << "\n";
	}
    return 0;
}