1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 const int inf=100000000; 5 const int MAXN=105; 6 int n,m,minc; 7 int map[MAXN][MAXN],dis[MAXN][MAXN]; 8  9 void init(){10     for(int i=1;i<=n;i++){11         for(int j=i;j<=n;j++)12         map[i][j]=map[j][i]=dis[i][j]=dis[j][i]=inf;13         map[i][i]=dis[i][i]=0;14     }15 }16 17 void floyd(){18     minc=inf;19     int tmp;20     for(int k=1;k<=n;k++){21         for(int i=1;i<k;i++){22             for(int j=i+1;j<k;j++){23                 tmp=dis[i][j]+map[i][k]+map[k][j];24                 if(tmp<minc)25                 minc=tmp;26             }27         }28         for(int i=1;i<=n;i++){29             for(int j=1;j<=n;j++){30                 tmp=dis[i][k]+dis[k][j];31                 if(tmp<dis[i][j])32                 dis[i][j]=tmp;33             }34         }35     }36 }37 38 39 int main(){40     int u,v,w;41     while(scanf("%d%d",&n,&m)!=EOF){42         init();43         for(int i=1;i<=m;i++){44             scanf("%d%d%d",&u,&v,&w);45             if(w<map[u][v])46             map[u][v]=map[v][u]=dis[u][v]=dis[v][u]=w;47         }48         floyd();49         if(minc==inf)50         printf("It‘s impossible.\n");51         else printf("%d\n",minc);52     }53     return 0;54 }