## Editorial for Đến trường

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 flashmt

const fi='';
fo='';
maxn=5005;
maxc=2000000000;
var n,m:longint;
a,w:array[1..40000] of integer;
d,s,cur,pos:array[1..maxn] of longint;
sl:array[1..maxn] of qword;
free:array[1..maxn] of boolean;
b:array[1..20000,0..3] of longint;

procedure rf;
var i,j,x,y,z,t:longint;
begin
for i:=1 to m do
begin
for j:=0 to 3 do
inc(s[b[i,1]]);
if b[i,0]=2 then inc(s[b[i,2]]);
end;
pos[1]:=1; cur[1]:=1;
for i:=2 to n+1 do
begin
pos[i]:=pos[i-1]+s[i-1];
cur[i]:=pos[i];
end;
for i:=1 to m do
begin
a[cur[b[i,1]]]:=b[i,2];
w[cur[b[i,1]]]:=b[i,3];
inc(cur[b[i,1]]);
if b[i,0]=2 then
begin
a[cur[b[i,2]]]:=b[i,1];
w[cur[b[i,2]]]:=b[i,3];
inc(cur[b[i,2]]);
end;
end;
end;

procedure pr;
var i,x,t,min:longint;
begin
for i:=1 to n do
begin
free[i]:=true;
d[i]:=maxc;
end;
d[1]:=0; free[1]:=false; x:=1; sl[1]:=1;
repeat
for i:=pos[x] to pos[x+1]-1 do
if free[a[i]] then
begin
if d[a[i]]=d[x]+w[i] then sl[a[i]]:=sl[a[i]]+sl[x]
else
begin
if d[a[i]]>d[x]+w[i] then
begin
d[a[i]]:=d[x]+w[i];
sl[a[i]]:=sl[x];
end;
end;
end;
min:=maxc-1; t:=0;
for i:=1 to n do
if free[i] and (d[i]<min) then
begin
min:=d[i];
t:=i;
end;
if t=0 then exit;
x:=t; free[x]:=false;
until not free[n];
end;

procedure wf;
begin
writeln(d[n],' ',sl[n]);
end;

begin
assign(input,fi); reset(input);
assign(output,fo); rewrite(output);
rf;
pr;
wf;
close(input); close(output);
end.

#### 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 d[N], n, m;
LL c[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() {
scanf("%d%d",&n,&m); g.resize(n);
rep(i,m) {
int k, u, v, l; scanf("%d%d%d%d",&k,&u,&v,&l);
g[--u].pb(ii(--v,l));
if(k == 2) g[v].pb(ii(u,l));
}
dijkstra(g, 0, d, c);
printf("%d %lld\n", d[n-1], c[n-1]);
return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 5050;
const int INF = 1e9;

struct Edge {
int to, cost;
Edge(int to, int cost): to(to), cost(cost) {}
};

namespace PriorityQueue {
static const int LIMIT = 2e5;
vector<int> V[LIMIT];
int size;
int cur;

void push(int u, int d) { V[d].push_back(u); ++size; }
void getMin(int &u, int &du) {
while (cur < LIMIT && V[cur].empty()) ++cur;
assert(cur < LIMIT);
--size;
u = V[cur].back(); du = cur;
V[cur].pop_back();
}
}

int d[N];
long long cnt[N];;
int n, m;

vector<Edge> a[N];

int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int k, u, v, L;
cin >> k >> u >> v >> L;
a[u].push_back(Edge(v, L));
if (k == 2) a[v].push_back(Edge(u, L));
}
for (int i = 2; i <= n; ++i) d[i] = INF;
PriorityQueue::push(1, 0); cnt[1] = 1;
while (PriorityQueue::size) {
int u, du;
PriorityQueue::getMin(u, du);
if (d[u] != du) continue;
for (auto e : a[u]) {
int v = e.to;
int c = e.cost;
if (d[v] > d[u] + c) {
d[v] = d[u] + c;
PriorityQueue::push(v, d[v]);
cnt[v] = cnt[u];
} else if (d[v] == d[u] + c) {
cnt[v] += cnt[u];
}
}
}
cout << d[n] << ' ' << cnt[n] << endl;
return 0;
}

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

{\$R-,Q-}
const
FINP='';
FOUT='';
MAXN=20000;
oo=1000000000;
type
list=^node;
node=record u,c:longint; next:list; end;
var
thuan,nghich:array[1..MAXN] of list;
d,hpos,h:array[1..MAXN] of longint;
sl:array[1..MAXN] of int64;
hsize,n:longint;
var
p:list;
begin
new(p); p^.u:=u; p^.c:=c; p^.next:=a; a:=p;
end;
procedure inp; inline;
var
f:text;
i,m,u,c,v,l:longint;
begin
assign(f,FINP); reset(f);
for i:=1 to n do
begin
thuan[i]:=nil;
nghich[i]:=nil;
end;
for i:=1 to m do
begin
if l=2 then
begin
end;
end;
close(f);
end;
procedure swap(var a,b:longint); inline;
var
temp:longint;
begin
temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint); inline;
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); inline;
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); inline;
begin
inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
upHeap(hsize);
end;
procedure pop(var u:longint); inline;
begin
u:=h[1]; hpos[u]:=0;
swap(h[1],h[hsize]);
hpos[h[1]]:=1; dec(hsize);
downHeap(1);
end;
procedure dijkstra; inline;
var
u,v,c:longint;
p:list;
begin
for u:=1 to n do d[u]:=oo;
for u:=1 to n do sl[u]:=-1; sl[1]:=1;
hsize:=0;
d[1]:=0; push(1);
while hsize>0 do
begin
pop(u);
p:=thuan[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 dfs(u:longint); inline;
var
p:list;
v,c:longint;
begin
if sl[u]<>-1 then exit;
sl[u]:=0;
p:=nghich[u];
while p<>nil do
begin
v:=p^.u; c:=p^.c;
p:=p^.next;
if d[v]+c=d[u] then
begin
dfs(v);
sl[u]:=sl[u]+sl[v];
end;
end;
end;
procedure ans; inline;
var
f:text;
begin
assign(f,FOUT); rewrite(f);
writeln(f,d[n],' ',sl[n]);
close(f);
end;
begin
inp;
dijkstra;
dfs(n);
ans;
end.

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

Program QBSCHOOL2;
Const
input  = '';
output = '';
max = 200000000;
Var
u,v,c: array[1..20000] of integer;
k: array[1..20000] of byte;
d: array[1..5000] of longint;
numway: array[1..5000] of int64;
free: array[1..5000] of boolean;
n,m: integer;

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

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

For i:= 1 to m do
Begin

inc(h[u[i]]);
If k[i] = 2 then inc(h[v[i]]);
End;

Close(f);

For i:= 2 to n do h[i]:= h[i] + h[i - 1];
t:= h[n];

For i:= 1 to m do
Begin
dec(h[u[i]]);

If k[i] = 2 then
Begin
dec(h[v[i]]);
End;
End;

h[n + 1]:= t;
End;

Procedure init;
Var
i: longint;
Begin
Fillchar(free, sizeof(free), true);

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

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

Procedure Dijkstra;
Var
i,u,v,min,iv: longint;
Begin
Repeat
u:= 0;
min:= max;

For i:= 1 to n do
if free[i] and (d[i] < min) then
Begin
u:= i;
min:= d[i];
End;

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];
End
else if d[v] = d[u] + adjcost[iv] then
numway[v]:= numway[v] + numway[u];
End;
Until false;
End;

Procedure solve;
Var
f: text;
Begin
Assign(f, output);
Rewrite(f);
Writeln(f, d[n], ' ', numway[n]);
Close(f);
End;

Begin
init;
Dijkstra;
solve;
End.

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

#include<stdio.h>
#include<vector>
#include<queue>
#define MAX   5555
const int INF=1e9;
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
int m,n;
vii g[MAX];
ll c[MAX];
int d[MAX];
int s,e;
scanf("%d",&n);
scanf("%d",&m);
int i,k,u,v,w;
for (i=1;i<=m;i=i+1) {
scanf("%d",&k);
scanf("%d",&u);
scanf("%d",&v);
scanf("%d",&w);
g[u].push_back(ii(v,w));
if (k==2) g[v].push_back(ii(u,w));
}
for (i=1;i<=n;i=i+1) {
d[i]=INF;
c[i]=0;
}
c[1]=1;
d[1]=0;
}
void dijkstra(void) {
int i,v,w;
ii x;
priority_queue<ii,vii,greater<ii> > q;
q.push(ii(0,1));
while (!q.empty()) {
x=q.top(); q.pop();
w=x.first;
v=x.second;
for (i=0;i<g[v].size();i=i+1) {
if (d[g[v][i].first]==w+g[v][i].second) {
c[g[v][i].first]+=c[v];
continue;
}
if (d[g[v][i].first]>w+g[v][i].second) {
d[g[v][i].first]=w+g[v][i].second;
c[g[v][i].first]=c[v];
q.push(ii(d[g[v][i].first],g[v][i].first));
continue;
}
}
}
printf("%d %lld",d[n],c[n]);
}
int main(void) {