#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=5e4+10;
vector< PII >G[N];
int n,m,st,ed,dis[N],vis[N];
void dijkstra()
{
    priority_queue<PII,vector<PII>,greater<PII>>q;
    memset(dis,0x3f,sizeof(dis));dis[st]=0;
    memset(vis,0,sizeof(vis));
    q.push({0,st});
    while(!q.empty())
    {
        int x=q.top().second;q.pop();
		if(vis[x])continue;
		vis[x]=1;
        for(auto i:G[x])
		{
			int y=i.first,w=i.second;
			if(dis[y]>dis[x]+w)
			{
				dis[y]=dis[x]+w;
				q.push({dis[y],y});
			}
		}
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,w;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&w);
        G[x].push_back({y,w});
        G[y].push_back({x,w});
    }
    st=1;ed=n;
    dijkstra();
    printf("%d\n",dis[ed]);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=5e4+10;
vector< PII >G[N];
int n,m,st,ed,dis[N],vis[N];
void dijkstra()
{
    priority_queue<PII,vector<PII>,greater<PII>>q;
    memset(dis,0x3f,sizeof(dis));dis[st]=0;
    memset(vis,0,sizeof(vis));
    q.push({0,st});
    while(!q.empty())
    {
        int x=q.top().second;q.pop();
		if(vis[x])continue;
		vis[x]=1;
        for(auto i:G[x])
		{
			int y=i.first,w=i.second;
			if(dis[y]>dis[x]+w)
			{
				dis[y]=dis[x]+w;
				q.push({dis[y],y});
			}
		}
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,w;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&w);
        G[x].push_back({y,w});
        G[y].push_back({x,w});
    }
    st=1;ed=n;
    dijkstra();
    printf("%d\n",dis[ed]);
    return 0;
}