## Editorial for CENTRE

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 30005
typedef long long LL;

int d1[N], d2[N], n, m;
LL c1[N], c2[N];
vvii g;

void dijkstra(vvii&g, int s, int *d, LL *c) {
fill(d,d+n,INF); d[s] = 0; c[s] = 1;
priority_queue< ii, vii, greater<ii> > qu;
qu.push(ii(0,s));
while(!qu.empty()) {
int u = qu.top().se, du = qu.top().fi; qu.pop();
if(du > d[u]) continue;
tr(g[u],it) {
int v = it->fi, l = it->se;
if( du + l < d[v] ) {
qu.push(ii(d[v] = du+l,v));
c[v] = c[u];
} else if( du + l == d[v] ) c[v] += c[u];
}
}
}

int main() {
#ifndef ONLINE_JUDGE
freopen( "input.txt", "r", stdin );
//freopen( "output.txt", "w", stdout );
#endif
scanf("%d%d",&n,&m); g.resize(n);
rep(i,m) {
int u, v, l; scanf("%d%d%d",&u,&v,&l);
g[--u].pb(ii(--v,l)); g[v].pb(ii(u,l));
}
dijkstra(g, 0, d1, c1);
dijkstra(g, n-1, d2, c2);
vi res;
rep(i,n)
if(!(d1[i]+d2[i]==d1[n-1] && c1[i]*c2[i]==c1[n-1])) res.pb(i+1);
printf("%d\n",sz(res));
tr(res,it) printf("%d\n",*it);
return 0;
}


{$MODE OBJFPC} program centre28; uses math; type e=record v,w,link:longint; end; const maxn=30003; maxm=200005; oo=trunc(1e9); fi=''; var adj:array[1..maxm] of e; head,pos,h:array[1..maxn] of longint; d,way:array[1..2,1..maxn] of longint; n,m,mm,nh:longint; procedure input; var inp:text; i,x,y,w:longint; begin assign(inp,fi);reset(inp); readln(inp,n,mm); for i:=1 to mm do begin readln(inp,x,y,w); inc(m); adj[m].v:=y; adj[m].w:=w; adj[m].link:=head[x]; head[x]:=m; inc(m); adj[m].v:=x; adj[m].w:=w; adj[m].link:=head[y]; head[y]:=m; end; close(inp); end; procedure update(dir,u:longint); var c,p:longint; begin c:=pos[u]; if c=0 then begin inc(nh); c:=nh; end; repeat p:=c shr 1; if (p=0) or (d[dir,h[p]]<=d[dir,u]) then break; h[c]:=h[p]; pos[h[c]]:=c; c:=p; until false; h[c]:=u; pos[u]:=c; end; function extract(dir:longint):longint; var v,p,c:longint; begin result:=h[1]; v:=h[nh]; dec(nh); p:=1; repeat c:=p shl 1; if (c<nh) and (d[dir,h[c+1]]<d[dir,h[c]]) then inc(c); if (c>nh) or (d[dir,h[c]]>=d[dir,v]) then break; h[p]:=h[c]; pos[h[p]]:=p; p:=c; until false; h[p]:=v; pos[v]:=p; end; procedure dijkstra(source,dir:longint); var u,i:longint; v:e; begin for i:=1 to n do d[dir,i]:=oo; for i:=1 to n do pos[i]:=0; d[dir,source]:=0; way[dir,source]:=1; nh:=0; update(dir,source); repeat u:=extract(dir); i:=head[u]; while i>0 do begin v:=adj[i]; if d[dir,v.v]>d[dir,u]+v.w then begin d[dir,v.v]:=d[dir,u]+v.w; update(dir,v.v); way[dir,v.v]:=way[dir,u]; end else if d[dir,v.v]=d[dir,u]+v.w then inc(way[dir,v.v],way[dir,u]); i:=v.link; end; until nh=0; end; procedure process; var i,res:longint; ver:array[1..maxn] of longint; begin res:=0; for i:=2 to n-1 do if (d[1,i]+d[2,i]>d[1,n]) or ((d[1,i]+d[2,i]=d[1,n]) and (way[1,i]*way[2,i]<way[1,n])) then begin inc(res); ver[res]:=i; end; writeln(res); for i:=1 to res do writeln(ver[i]); end; begin input; dijkstra(1,1); dijkstra(n,2); process; end.  #### Code mẫu của RR {$R+,Q+}
const
FINP='';
FOUT='';
MAXN=30000;
oo=1000000000;
type
list=^node;
node=record u,c:longint; next:list; end;
mang=array[1..MAXN] of int64;
var
p:list;
ke:array[1..MAXN] of list;
hsize,n:longint;
d,h,hpos:array[1..MAXN] of longint;
f,g:mang;
var
p:list;
begin
new(p); p^.u:=u; p^.c:=c; p^.next:=a; a:=p;
end;
procedure inp;
var
f:text;
i,m,u,v,c:longint;
begin
assign(f,FINP); reset(f);
for i:=1 to n do ke[i]:=nil;
for i:=1 to m do
begin
if u=v then continue;
end;
close(f);
end;
procedure swap(var a,b:longint);
var
temp:longint;
begin
temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint);
var
j:longint;
begin
j:=i shl 1;
while (j<=hsize) do
begin
if (j<hsize) and (d[h[j+1]]<d[h[j]]) then inc(j);
if d[h[j]]<d[h[i]] then
begin
swap(hpos[h[i]],hpos[h[j]]);
swap(h[i],h[j]);
end;
i:=j; j:=i shl 1;
end;
end;
procedure upHeap(i:longint);
var
j:longint;
begin
j:=i shr 1;
while (i>1) and (d[h[i]]<d[h[j]]) do
begin
swap(hpos[h[i]],hpos[h[j]]);
swap(h[i],h[j]);
i:=j; j:=i shr 1;
end;
end;
procedure push(u:longint);
begin
inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
upHeap(hsize);
end;
procedure pop(var u:longint);
begin
u:=h[1]; hpos[u]:=0;
swap(h[1],h[hsize]);
hpos[h[1]]:=1; dec(hsize);
downHeap(1);
end;
procedure dijkstra;
var
u,v,c:longint;
p:list;
begin
while hsize>0 do
begin
pop(u);
p:=ke[u];
while p<>nil do
begin
v:=p^.u; c:=p^.c; p:=p^.next;
if d[v]>d[u]+c then
begin
d[v]:=d[u]+c;
if hpos[v]=0 then push(v)
else upHeap(hpos[v]);
end;
end;
end;
end;
procedure ans;
var
fo:text;
count,i:longint;
begin
assign(fo,FOUT); rewrite(fo);
count:=0;
for i:=2 to n-1 do
if (f[i]*g[i]<>f[n]) or (f[i]=-1) or (g[i]=-1) then inc(count);
writeln(fo,count);
for i:=2 to n-1 do
if (f[i]*g[i]<>f[n]) or (f[i]=-1) or (g[i]=-1) then writeln(fo,i);
close(fo);
end;
procedure dfs1(u:longint); inline;
var
p:list;
v,c:longint;
begin
if f[u]<>-1 then exit;
f[u]:=0;
p:=ke[u];
while p<>nil do
begin
v:=p^.u; c:=p^.c;
p:=p^.next;
if d[v]+c=d[u] then
begin
dfs1(v);
f[u]:=f[u]+f[v];
end;
end;
end;
procedure dfs2(u:longint);
var
p:list;
v,c:longint;
begin
if g[u]<>-1 then exit;
g[u]:=0;
p:=ke[u];
while p<>nil do
begin
v:=p^.u; c:=p^.c;
p:=p^.next;
if d[v]+c=d[u] then
begin
dfs2(v);
g[u]:=g[u]+g[v];
end;
end;
end;
procedure solve;
var
u:longint;
begin
for u:=1 to n do d[u]:=oo;
for u:=1 to n do f[u]:=-1;
hsize:=1; h[1]:=1; d[1]:=0; hpos[1]:=1;
f[1]:=1;
dijkstra;
dfs1(n);
for u:=1 to n do d[u]:=oo;
for u:=1 to n do g[u]:=-1;
fillchar(hpos,sizeof(hpos),0);
hsize:=1; h[1]:=n; d[n]:=0; hpos[n]:=1;
g[n]:=1;
dijkstra;
dfs2(1);
end;
begin
inp;
solve;
ans;
end.


#### Code mẫu của ll931110

{\$MODE DELPHI}
Program CENTRE28;
Type
vertex = array[1..30001] of longint;
edge = array[0..200000] of longint;
select = array[1..30000] of boolean;
Const
input  = '';
output = '';
max = 10000000000000;
Var
n,m,nHeap: longint;
pos,heap,h,queue: vertex;
n1,nn,d1,dn,d,numway: array[1..30001] of int64;
x,y,c: array[1..100000] of longint;
free,check: select;

Var
f: text;
i: longint;
Begin
Assign(f, input);
Reset(f);

Fillchar(h, sizeof(h), 0);

For i:= 1 to m do
Begin
inc(h[x[i]]);
inc(h[y[i]]);
End;
Close(f);

For i:= 2 to n do h[i]:= h[i] + h[i - 1];
For i:= 1 to m do
Begin
dec(h[x[i]]);

dec(h[y[i]]);
End;
h[n + 1]:= 2 * m;
End;

procedure Update(v: Integer);
var
parent, child: Integer;
begin
child := Pos[v];
if child = 0 then
begin
Inc(nHeap); child := nHeap;
end;
parent := child div 2;
while (parent > 0) and (d[heap[parent]] > d[v]) do
begin
heap[child] := heap[parent];
Pos[heap[child]] := child;
child := parent;
parent := child div 2;
end;
heap[child] := v;
Pos[v] := child;
end;

function Pop: Integer;
var
r, c, v: Integer;
begin
Pop := heap[1];
v := heap[nHeap];
Dec(nHeap);
r := 1;
while r * 2 <= nHeap do
begin
c := r * 2;
if (c < nHeap) and (d[heap[c + 1]] < d[heap[c]]) then Inc(c);
if d[v] <= d[heap[c]] then Break;
heap[r] := heap[c];
Pos[heap[r]] := r;
r := c;
end;
heap[r] := v;
Pos[v] := r;
end;

Procedure Dijkstra(s: integer);
Var
i,u,iv,v: longint;
Begin
Fillchar(pos, sizeof(pos), 0);
Fillchar(free, sizeof(free), true);

Fillchar(numway, sizeof(numway), 0);
numway[s]:= 1;

For i:= 1 to n do d[i]:= max;
d[s]:= 0;
nHeap:= 0;

Update(s);
Repeat
u:= pop;
If u = 0 then break;
free[u]:= false;

For iv:= h[u] + 1 to h[u + 1] do
Begin
If free[v] then
If d[v] > d[u] + adjcost[iv] then
Begin
numway[v]:= numway[u];
Update(v);
End
else if d[v] = d[u] + adjcost[iv] then
numway[v]:= numway[v] + numway[u];
End;
Until nHeap = 0;
End;

Procedure printresult;
Var
f: text;
k,i: longint;
Begin
Dijkstra(1);
d1:= d;
n1:= numway;

Dijkstra(n);
dn:= d;
nn:= numway;

Assign(f, output);
Rewrite(f);

Fillchar(free, sizeof(free), false);
k:= 0;

For i:= 2 to n - 1 do
if (d1[i] + dn[i] <> d1[n])
or (int64(n1[i] * nn[i]) <> n1[n]) then
Begin
inc(k);
free[i]:= true;
End;

Writeln(f, k);
For i:= 2 to n - 1 do if free[i] then writeln(f, i);

Close(f);
End;

Begin
printresult;
End.


#### Code mẫu của skyvn97

#include<cstdio>
#include<queue>
#include<vector>
#define MAX   30303
#define INF   1e9
#define v   second
#define w   first
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef priority_queue<ii,vii,greater<ii> > pq;
int m,n,r;
vii g[MAX];
int d[7][MAX];
int c[7][MAX];
bool a[MAX];
int i,u,v,w;
scanf("%d",&n);
scanf("%d",&m);
for (i=1;i<=m;i=i+1) {
scanf("%d",&u);
scanf("%d",&v);
scanf("%d",&w);
g[u].push_back(ii(w,v));
g[v].push_back(ii(w,u));
}
for (i=1;i<=n;i=i+1) {
d[0][i]=INF;
d[1][i]=INF;
c[0][i]=0;
c[1][i]=0;
}
}
void dijkstra(int s) {
pq q=pq();
ii p;
int i,u,w;
d[s%n][s]=0;
c[s%n][s]=1;
q.push(ii(0,s));
while (!q.empty()) {
p=q.top();q.pop();
u=p.v;
w=p.w;
for (i=0;i<g[u].size();i=i+1) {
if (w+g[u][i].w==d[s%n][g[u][i].v]) c[s%n][g[u][i].v]+=c[s%n][u];
if (w+g[u][i].w<d[s%n][g[u][i].v]) {
d[s%n][g[u][i].v]=w+g[u][i].w;
c[s%n][g[u][i].v]=c[s%n][u];
q.push(ii(d[s%n][g[u][i].v],g[u][i].v));
}
}
}
}
void process(void) {
dijkstra(1);
dijkstra(n);
r=0;
int i;
for (i=2;i<n;i=i+1) {
if (d[1][i]+d[0][i]>d[1][n]) {
r=r+1;
a[i]=true;
}
else {
if (c[1][i]*c[0][i]<c[1][n]) {
r=r+1;
a[i]=true;
}
else a[i]=false;
}
}
printf("%d\n",r);
for (i=2;i<n;i=i+1)
if (a[i]) printf("%d\n",i);
}
int main(void) {
process();
return 0;
}


#### Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const int MAX = 30001;

struct Node {
int v, x, d;
Node *next;
Node() {}
Node(int v, int x, int d) {
this->v = v;
this->x = x;
this->d = d;
this->next = NULL;
}
};

int inf, n, m, dem;
int d[MAX], d2[MAX];
Node *ke[MAX];
int low[MAX], num[MAX], fa[MAX];
bool khop[MAX], mark[MAX], vs[MAX];

void add( Node * & p, Node * q) {
Node * tmp = p;
p = q;
q->next = tmp;
}

void dfs( int i ) {
num[i] = dem++;
low[i] = num[i];
vs[i] = true;
for(Node * p = ke[i]; p!=NULL; p = p->next) {
int j = p->v;
int z = p->d;
/*if(d[j]==d[i]+z) {
fa[j] = i;
dfs(j);
low[i] <?= low[j];
}
else if(d[j]+z==d[i] && j!=fa[i]) {
low[i] <?= num[j];
}*/
if(!mark[j]) continue;
if(d[j]==d[i]+z || d[i]==d[j]+z) {
if(!vs[j]) {
fa[j] = i;
dfs(j);
low[i] <?= low[j];
}
else if(j!=fa[i]) {
low[i] <?= num[j];
}
}
}
if(fa[i]>0) {
int fi = fa[i];
if(low[i]>=num[fi]) khop[fi] = true;
}
}

void bfs( int st, int d[MAX]) {
queue<int> q;
q.push(st);
memset( d, 0x3f, sizeof(d2));
inf = d[0];
d[st] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for(Node * p = ke[u]; p!=NULL; p = p->next) {
int v = p->v;
int z = p->d;
if(d[v]>d[u]+z) {
d[v] = d[u] + z;
q.push(v);
}
}
}
}

int main() {
scanf("%d%d", &n, &m);
for(int i=0;i<m;++i) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add( ke[x], new Node(y, x^y, z));
add( ke[y], new Node(x, x^y, z));
}
bfs( 1, d);
bfs( n, d2);
for(int i=1;i<=n;++i) if(d[i]+d2[i] == d[n]) mark[i] = true;
int res = 0;
dfs(1);
for(int i=2;i<n;++i) if(!khop[i] || !mark[i]) ++res;
printf("%d\n", res);
for(int i=2;i<n;++i) if(!khop[i] || !mark[i]) printf("%d\n", i);
//system("pause");
return 0;
}