#include<bits/stdc++.h>
using namespace std;
int i,j,ans,a,b,z,n,m,pan[110],w,mi,f[110][110],dis[110];
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
f[i][j]=0xfffffff;
for(i=1;i<=n;i++)dis[i]=0xfffffff;
for(i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&z);
f[a][b]=f[b][a]=z;
}
for(i=1;i<=n;i++)dis[i]=f[1][i];
dis[1]=0;pan[1]=1;
for(i=1;i<=n;i++){
w=0;mi=0xfffffff;
for(j=1;j<=n;j++)if(!pan[j]&&dis[j]<mi)mi=dis[w=j];
if(!w)break;pan[w]=1;
for(j=1;j<=n;j++)dis[j]=min(dis[j],dis[w]+f[w][j]);
}
for(i=1;i<=n;i++)ans=max(ans,dis[i]);
if(ans==0xfffffff)printf("-1");
else printf("%d",ans);
return 0;
}
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=103,inf=1e8;
int n,m,x,y,z,ans,Ans[N],a[N][N],g[N][N],dis[N][N];
inline void in(Re &x){
Re fu=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=fu?-x:x;
}
inline void get(Re i,Re j){
Re k=g[i][j];if(!k)return;
get(i,k),Ans[++Ans[0]]=k,get(k,j);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m);
for(Re i=1;i<=n;++i)
for(Re j=1;j<=n;++j)
dis[i][j]=a[i][j]=inf;
for(Re i=1;i<=n;++i)dis[i][i]=a[i][i]=0;
while(m--)in(x),in(y),in(z),dis[x][y]=dis[y][x]=a[x][y]=a[y][x]=min(a[x][y],z);
ans=inf;
for(Re k=1;k<=n;++k){
for(Re i=1;i<k;++i)
for(Re j=i+1,tmp;j<k;++j)
if((tmp=dis[i][j]+a[j][k]+a[k][i])<ans){
ans=tmp,Ans[0]=0;
Ans[++Ans[0]]=i;
get(i,j);
Ans[++Ans[0]]=j;
Ans[++Ans[0]]=k;
}
for(Re i=1;i<=n;++i)
for(Re j=1,tmp;j<=n;++j)
if((tmp=dis[i][k]+dis[k][j])<dis[i][j])
dis[i][j]=tmp,g[i][j]=k;
}
if(ans==inf)puts("No solution.");
else for(Re i=1;i<=Ans[0];++i)printf("%d ",Ans[i]);
}
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e5+5,M=1e5+5,inf=2e9;
int x,y,z,n,m,o,to,st,dis[N],pan[N],head[N];
struct QAQ{int w,to,next;}a[M<<1];
struct QWQ{int x,d;inline bool operator<(QWQ O)const{return d>O.d;}};
priority_queue<QWQ>Q;
inline void in(Re &x){
Re fu=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=fu?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline void dijkstra(Re st){
for(Re i=0;i<=n;++i)dis[i]=inf;
dis[st]=0,Q.push((QWQ){st,0});
while(!Q.empty()){
x=Q.top().x,Q.pop();
if(pan[x])continue;
pan[x]=1;
for(Re i=head[x];i;i=a[i].next)
if(dis[to=a[i].to]>dis[x]+a[i].w){
dis[to]=dis[x]+a[i].w;
Q.push((QWQ){to,dis[to]});
}
}
}
int main(){
in(n),in(m),in(st);
while(m--)in(x),in(y),in(z),add(x,y,z);
dijkstra(st);
for(Re i=1;i<=n;++i)printf("%d ",dis[i]);
}
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e4+5,M=5e5+5,inf=2147483647;
int x,y,z,n,m,o,to,st,dis[N],pan[N],head[N];
struct QAQ{int w,to,next;}a[M<<1];
queue<int>Q;
inline void in(Re &x){
Re fu=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=fu?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline void SPFA(Re st){
for(Re i=0;i<=n;++i)dis[i]=inf;
dis[st]=0,pan[st]=1,Q.push(st);
while(!Q.empty()){
x=Q.front(),Q.pop();
pan[x]=0;
for(Re i=head[x];i;i=a[i].next)
if(dis[to=a[i].to]>dis[x]+a[i].w){
dis[to]=dis[x]+a[i].w;
if(!pan[to])pan[to]=1,Q.push(to);
}
}
}
int main(){
in(n),in(m),in(st);
while(m--)in(x),in(y),in(z),add(x,y,z);
SPFA(st);
for(Re i=1;i<=n;++i)printf("%d ",dis[i]);
}
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=5003,M=1e5+3,inf=1e9;
int n,m,x,y,z,o,pan[N],head[N],dis[N][2];
struct QAQ{int w,to,next;}a[M<<1];queue<int>Q;
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
Re fu=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=fu?-x:x;
}
inline void SPFA(Re st){
for(Re i=0;i<=n;++i)dis[i][0]=dis[i][1]=inf;
dis[st][0]=0,pan[st]=1,Q.push(st);
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to,tmp;i;i=a[i].next){
if(dis[to=a[i].to][0]>(tmp=dis[x][0]+a[i].w)){
dis[to][1]=dis[to][0];
dis[to][0]=tmp;
if(!pan[to])pan[to]=1,Q.push(to);
}
if(dis[to][1]>(tmp=dis[x][0]+a[i].w)&&tmp>dis[to][0]){
dis[to][1]=tmp;
if(!pan[to])pan[to]=1,Q.push(to);
}
if(dis[to][1]>(tmp=dis[x][1]+a[i].w)){
dis[to][1]=tmp;
if(!pan[to])pan[to]=1,Q.push(to);
}
}
}
}
int main(){
in(n),in(m);
while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
SPFA(1);
printf("%d\n",dis[n][1]);
}