#include<vector>
#include <string>
#include<algorithm>
#include <iostream>
#include <queue>
#include<set>
#include<cmath>
#include<math.h>
using namespace std;
#define ll long long
#define pll pair<long long, long long>
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define cin(a) for(ll ghgh = 0; ghgh<a.size(); ghgh++) cin»a[ghgh];
#define pcin(a) for(ll ghgh = 0; ghgh<a.size(); ghgh++) cin»a[ghgh].first»a[ghgh].second;
#define cout(a) for(ll ghgha = 0; ghgha<a.size(); ghgha++) cout«a[ghgha]«" ";
#define pcout(a) for(ll ghgha = 0; ghgha<a.size(); ghgha++) cout«a[ghgha].first«" "«a[ghgha].second«endl;
const ll inf = 1e9 + 7, llinf = 1e18 + 123;
void xru() {
setlocale(LC_ALL, "rus");
/*freopen(".in", "r", stdin);
freopen(".out", "w", stdout);*/
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}


struct tp {
ll a, b, c;
};



int main()
{
xru();

ll n, m;
cin » n » m;
vector<vector<pll»g(n), check(n, vector<pll>(n, { 0, 0 }));
vector<tp>id(m);
for (ll i = 0; i < m; i++) {
ll x, y, cnt;
cin » x » y » cnt;
x--, y--;
id[i].a = x;
id[i].b = y;
id[i].c = cnt;
if (x == y) {
continue;
}
if (check[x][y].first != 0) {
check[x][y].second = min(check[x][y].second, cnt);
check[y][x].second = check[x][y].second;
}
else {
check[x][y] = { 1, cnt };
check[y][x] = check[x][y];
}
}
for (ll i = 0; i < m; i++) {
if (id[i].a == id[i].b) {
continue;
}
if (check[ id[i].a ][ id[i].b ].first == 1) {
g[id[i].a].push_back({ id[i].b, check[id[i].a][id[i].b].second });
g[id[i].b].push_back({ id[i].a, check[id[i].a][id[i].b].second });
check[id[i].a][id[i].b].first--;
check[id[i].b][id[i].a].first--;

}
}

queue<pll>q;
vector<ll>dist(n, inf);
vector<bool>used(n, false);
dist[n - 1] = 0;
vector<pll>prev(n);
prev[n-1] = { -1, -1 };
q.push({ n - 1, 0 });
while (!q.empty()) {
pll x = q.front();
q.pop();
for (ll i = 0; i < g[x.first].size(); i++) {
pll to = g[x.first][i];
if (dist[x.first] + 1 < dist[to.first]) {
prev[to.first].first = x.first;
prev[to.first].second = to.second;
dist[to.first] = dist[x.first] + 1;
}
else if (dist[x.first] + 1 == dist[to.first]) {
if (to.second < prev[to.first].second) {
prev[to.first].first = x.first;
prev[to.first].second = to.second;
}
}
if (!used[to.first]) {
used[to.first] = true;
q.push(to);
}
}


}
ll x = 0;
vector<ll>ans;
while (prev[x].first != -1) {
ans.push_back(prev[x].second);
x = prev[x].first;

}
cout « ans.size()«endl;
cout(ans);
}