#include <cstdio>

#include <queue>

#include <algorithm>

#include <cstring>

#include <map>

#define N 400003

#define inf 10000000000000

#define ll long long

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

namespace IO

{

    char *p1, *p2, buf[100000];

    #define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

    int rd() {

        int x = 0, f = 1;

        char c = nc();

        while (c < 48) {

            if (c == '-')

                f = -1;

            c = nc();

        }

        while (c > 47) {

            x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();

        }

        return x * f;

    }

};

struct Edge

{

    int to,dis;

    Edge(int to=0,int dis=0):to(to),dis(dis){}

};

vector<Edge>G[N];

bool cmp(Edge a,Edge b)

{

    return a.dis<b.dis;

}

map<int,int>id[N];

int n,m,cnt,edges,s,t;

int hd[N*6],nex[N*6],to[N*6],done[N*6];

ll d[N*6],val[N*6];

inline void addedge(int u,int v,int c)

{

    nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=1ll*c;

}

struct Node

{

    ll dis;

    int u;

    Node(ll dis=0,int u=0):dis(dis),u(u){}

    bool operator<(Node b) const

    {

        return dis>b.dis;

    }

};

priority_queue<Node>q;

inline void Dijkstra()

{

    int i;

    for(i=0;i<=t;++i) d[i]=inf, done[i]=0;

    d[s]=0, q.push(Node(0,s));

    while(!q.empty())

    {

        Node e=q.top();q.pop();

        if(done[e.u]) continue;

        done[e.u]=1;

        int u=e.u;

        for(i=hd[u];i;i=nex[i])

        {

            int v=to[i];

            if(d[u]+val[i]<d[v])

            {

                d[v]=d[u]+val[i];

                q.push(Node(d[v],v));

            }

        }

    }

}

int main()

{

    int i,j;

    // setIO("input");

    n=IO::rd(),m=IO::rd();

    for(i=1;i<=m;++i)

    {

        int a=IO::rd(),b=IO::rd(),c=IO::rd();

        G[a].push_back(Edge(b,c)), G[b].push_back(Edge(a,c));

    }

    for(i=1;i<=n;++i)

    {

        sort(G[i].begin(),G[i].end(),cmp);

        if(G[i].empty()) continue;

        id[i][G[i][0].dis]=++cnt;

        for(j=1;j<(int)G[i].size();++j) if(G[i][j].dis!=G[i][j-1].dis) id[i][G[i][j].dis]=++cnt;

    }

    for(i=1;i<=n;++i)

    {

        int k,lst=0,pre=0;

        for(k=0;k<(int)G[i].size();k=j+1)

        {

            j=k;

            int cur=id[i][G[i][j].dis];

            while(j<(int)G[i].size()-1&&G[i][j+1].dis==G[i][j].dis) ++j;

            if(lst) addedge(cur,lst,0), addedge(lst,cur,G[i][k].dis-pre);

            for(int o=k;o<=j;++o) addedge(cur, id[G[i][o].to][G[i][o].dis], G[i][o].dis);

            lst=cur, pre=G[i][k].dis;

        }

    }

    s=0, t=cnt+2;

    for(i=0;i<G[1].size();++i)  if(i==0||G[1][i].dis!=G[1][i-1].dis) addedge(s,id[1][G[1][i].dis],G[1][i].dis);

    for(i=0;i<G[n].size();++i)  if(i==0||G[n][i].dis!=G[n][i-1].dis) addedge(id[n][G[n][i].dis],t,0);

    Dijkstra(), printf("%lld\n",d[t]);

    return 0;

}