#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
int n,m;
const int N=1e6+7;
struct nod{
    int u;
    int v;
    int w;
};
vector<nod> vv;
map<pair<int,int>,int> mp;
typedef struct edge
{
    int pos;//点
    int w;//距离
} edge;
typedef struct node
{
    int pos;//点
    int dis;//距离
    //一般来说比较函数写在结构体内会比写在外部快
    bool operator<(const node &x) const
    {
        return x.dis < dis;
        //x相当于当前正在比较的值，这个函数就是x从小到大排。
        //存储用优先队列时会相反，同是上面这个函数会按r从大到小排。
    }
} node;
vector<edge> connects[1000100];//创建一个容器，vector中标示了u与v之间的距离w
void add_edge(int u, int v, int w)
{
    connects[v].push_back({u, w});//表示v与u之间距离为w
    connects[u].push_back({v, w});//表示u与v之间距离为w
    return;
}
bool vis[300007];//记录是否访问了这个点
int dist[300007];//记录起点到点n的距离
const int INF = 0x3f3f3f3f;
// void init(int n)
// {
//     for (int i = 1; i <= n; i++)
//     {
//         vis[i] = 0;//初始化全部点开始时都没有访问过
//         connects[i].clear();//将上一次的数据清空
//         dist[i] = INF;//将起点还接触不到的点与起点的距离设置为无穷大
//     }
//     return;
// }
//这里使用了队列对dijkstra算法进行了优化
void Dijkstra_queue(int start)
{
    dist[start] = 0;//起点与起点的距离设置为0
    priority_queue<node> q;//创建一个优先队列
    q.push((node){start, 0});//放入队列当中
    while (!q.empty())//对队列进行操作，当队列为空后停止
    {
        int pos = q.top().pos;
        int dis = q.top().dis;
        q.pop();
        if (vis[pos])//访问过直接跳过
            continue;
        vis[pos] = 1;//标记为访问过
        for (int i = 0; i < connects[pos].size(); i++)
        {
            int v = connects[pos][i].pos;
            int w = connects[pos][i].w;
            if (dist[v] > dist[pos] + w)//如果1到点v的距离大于1到点pos加上pos到点v的距离,距离进项更新
            {
                dist[v] = dist[pos] + w;//1到点v的最短距离就等于1到点pos加上pos到点v的距离
                q.push((node){v, dist[v]});//计入到队列当中
            }
        }
    }
    return;
}
void solve(){
    cin>>n>>m;
    //init(n);
    memset(dist,INF,sizeof dist);
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        if(mp[{u,v}]==0){
            mp[{u,v}]=w;
            mp[{v,u}]=w;
        }else{
            if(w>mp[{u,v}]){
                mp[{u,v}]=w;
                mp[{v,u}]=w;
            }
        }
        vv.push_back({u,v,w});
    }
    for(int i=0;i<m;i++){
        int u=vv[i].u;
        int v=vv[i].v;
        int w=vv[i].w;
        if(mp[{u,v}]==w){
            add_edge(u,v,w);
            //cout<<u<<"!"<<v<<"!"<<endl;
        }
    }
    Dijkstra_queue(1);
    cout<<dist[n]<<endl;
}
signed main(){
    fast;
    int t=1;
    //cin>>t;
    solve();
}