这才是真正的最优解

/*
#include <bits/stdc++.h>
using namespace std;
long long bj[2005];
long long a[2005];
long long b[2005][2005];
int main(){
long long n,m;
cin>>n>>m;
while(m--){
long long u,v,w;
cin>>u>>v>>w;
if(b[u][v]==0 && b[v][u]==0) b[u][v]=b[v][u]=w;
else b[u][v]=b[v][u]=min(b[u][v],w);
}
for(int i=0;i<=n;i++){
a[i]=1e9;
}
a[1]=0;
for(int i=1;i<=m;i++){
int u=0;
for(int j=1;j<=n;j++){
if(bj[j]==0 && a[j]<a[u]){
u=j;
}
}
bj[u]=1;
for(int j=1;j<=n;j++){
if(bj[j]==0 && b[u][j]!=0 && a[j]>a[u]+b[u][j]){
a[j]=a[u]+b[u][j];
}
}
}
long long mnb=0;
for(int i=1;i<=n;i++){
if(a[i]!=1e9){
mnb+=a[i];
}
}
cout<<mnb;
return 0;
}
*/
#include <bits/stdc++.h>
using namespace std;
long long a[1005];
long long b[1005][1005];
long long bj[1005];
int main(){
long long n,m;
cin>>n>>m;
while(m--){
long long u,v,w;
cin>>u>>v>>w;
if(b[u][v]==0) b[u][v]=b[v][u]=w;
else b[u][v]=b[v][u]=min(b[u][v],w);
}
for(int i=0;i<=n;i++){
a[i]=1e9;
}
a[1]=0;
for(int i=1;i<=n;i++){
int u=0;
for(int j=1;j<=n;j++){
if(a[j]<a[u] && bj[j]==0){
u=j;
}
}
bj[u]=1;
for(int j=1;j<=n;j++){
if(b[u][j]!=0 && bj[j]==0 && a[j]>a[u]+b[u][j]){
a[j]=a[u]+b[u][j];
}
}
}
if(a[n]==1e9){
cout<<-1;
}else{
cout<<a[n];
}
return 0;
}