ll dij (int sta)
{
	rep (i, 1, n) f[i] = 1e17;
	f[0] = 1e17 + 1; f[sta] = 0;
	memset (vis, 0, sizeof vis);
	rep (i, 1, n - 1)
	{
		ll u = 0;
		rep (j, 1, n)
			if (vis[j] == 0 && f[j] < f[u]) u = j;
		vis[u] = true;
		for (int j = h[u]; j; j = net[j])
		{
			ll v = to[j], w = dis[j];
			if (f[u] + w < f[v])
				f[v] = f[u] + w;
		}
	} return f[(sta ^ n) ? n : 1];
}