#include <bits/stdc++.h> using namespace std; #define ALL(i_) i_.begin(), i_.end() #define PB push_back #define TASK "" typedef long long ll; typedef long double ld; typedef pair<int, int> ii; const int oo = 1000000099; const int mod = 1000000007; const int maxn = 100011; int numNode, numEdge; vector<ii> adj[maxn]; pair<vector<int>, vector<int>> Dijkstra(int sta) { vector<int> d(numNode + 11, oo); vector<int> cnt(numNode + 11, 0); d[sta] = 0, cnt[sta] = 1; priority_queue<ii, vector<ii>, greater<ii>> que; que.push({ 0, sta }); while (!que.empty()) { int u = que.top().second; int du = que.top().first; que.pop(); if (d[u] != du) continue; for (ii x : adj[u]) { int v = x.first; int dv = x.second; if (d[v] == du + dv) cnt[v] += cnt[u]; else if (d[v] > du + dv) { d[v] = du + dv; cnt[v] = cnt[u]; que.push({ d[v], v }); } } } return make_pair(d, cnt); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(TASK ".inp", "r")) { freopen(TASK ".inp", "r", stdin); freopen(TASK ".out", "w", stdout); } cin >> numNode >> numEdge; for (int i = 1; i <= numEdge; i++) { int u, v, w; cin >> u >> v >> w; adj[u].PB({ v, w }); adj[v].PB({ u, w }); } vector<int> d1, dn, cnt1, cntn; tie(d1, cnt1) = Dijkstra(1); tie(dn, cntn) = Dijkstra(numNode); vector<int> res; for (int i = 1; i <= numNode; i++) { if ((d1[i] + dn[i] > d1[numNode]) || (cnt1[i] * cntn[i] < cnt1[numNode])) res.PB(i); } cout << (int)res.size() << "\n"; for (auto x : res) cout << x << "\n"; return 0; }