#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=55;
const int inf=0x3f3f3f3f;
int g[N][N];
int dist[N];
bool st[N];
int n;
struct lu{int x;
          int y;
          int z;
          bool gu;};//用该结构体类型存储路径。gu表示是否晚上会封路
int dij(){memset(dist,0x3f,sizeof dist);
          memset(st,0,sizeof st);
          dist[1]=0;
         for(int i=0;i<n;i++){int t=-1;
             for(int j=1;j<=n;j++){if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;}
                st[t]=1;
                for(int j=1;j<=n;j++){dist[j]...