#include <bits/stdc++.h>
#define pii pair<int,int>
#define MAXN 100

const int INF = 1e9;

using namespace std;

vector<pii> grafo[MAXN];

int dist[MAXN];

void bfs01(int s){
deque<pii> q;
q.push_front({0,s});
dist[s] = 0;
while(!q.empty()){
pii e = q.front();
int v = e.second;
q.pop_front();
for(pii viz : grafo[v]){
int u = viz.second;
int w = viz.first;
if(dist[v]+w < dist[u]){
dist[u] = dist[v]+w;
if(w == 0){
q.push_front(viz);
}
else{
q.push_back(viz);
}
}
}
}
}

int main(){
int n, m; scanf("%d %d", &n, &m);

for(int i = 0; i < m; i++){
int a, b, c; scanf("%d %d %d", &a, &b, &c); //aresta que liga a em b com custo c
grafo[a].push_back({c, b});
grafo[b].push_back({c, a});
}

for(int i = 0; i <= n; i++){
dist[i] = INF;
}

bfs01(1);

printf("%d", dist[n]);
}