#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + ;

namespace IO

{

    const int Maxlen = N * ;

    char buf[Maxlen], *C = buf;

    int Len;

    inline void read_in()

    {

        Len = fread(C, , Maxlen, stdin);

        buf[Len] = '\0';

    }

    inline void fread(int &x)

    {

        x = ;

        int f = ;

        while (*C < '' || '' < *C) { if(*C == '-') f = -; ++C; }

        while ('' <= *C && *C <= '') x = (x << ) + (x << ) + *C - '', ++C;

        x *= f;

    }

    inline void fread(long long &x)

    {

        x = ;

        long long f = ;

        while (*C < '' || '' < *C) { if(*C == '-') f = -; ++C; }

        while ('' <= *C && *C <= '') x = (x << ) + (x << ) + *C - '', ++C;

        x *= f;

    }

    inline void read(int &x)

    {

        x = ;

        int f = ; char c = getchar();

        while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }

        while(c >= '' && c <= '') { x = (x << ) + (x << ) + c - ''; c = getchar(); }

        x *= f;

    }

    inline void read(long long &x)

    {

        x = ;

        long long f = ; char c = getchar();

        while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }

        while(c >= '' && c <= '') { x = (x << 1ll) + (x << 3ll) + c - ''; c = getchar(); }

        x *= f;

    }

} using namespace IO;

int rd()

{

    int x = , f = ;

    char c = getchar();

    while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }

    while(c >= '' && c <= '') { x = x *  + c - ''; c = getchar(); }

    return x * f;

}

int n, cnt = , source, sink, m;

int head[N], hd[N * ], st[N], vis[N * ];

ll d[N * ];

struct edge {

    int nxt, to, w;

} e[N * ];

bool cmp(int i, int j)

{

    return e[i].w < e[j].w;

}

void link(int *head, int u, int v, int w)

{

    e[++cnt].nxt = head[u];

    head[u] = cnt;

    e[cnt].to = v;

    e[cnt].w = w;

}

int main()

{

    read_in();

    fread(n);

    fread(m);

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

    {

        int u, v, w;

        fread(u);

        fread(v);

        fread(w);

        link(head, u, v, w);

        link(head, v, u, w);

    }

    source = ;

    sink =  * m + ;

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

    {

        int top = ;

        for(int j = head[i]; j; j = e[j].nxt) st[++top] = j;

        sort(st + , st + top + , cmp);

        for(int j = ; j <= top; ++j)

        {

            int now = st[j], nxt = st[j + ];

            if(i == ) link(hd, source, now, e[now].w);

            if(e[now].to == n) link(hd, now, sink, e[now].w);

            link(hd, now, now ^ , e[now].w);

            if(j < top)

            {

                link(hd, now, nxt, e[nxt].w - e[now].w);

                link(hd, nxt, now, );

            }

        }

    }

    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > q;

    memset(d, 0x3f3f, sizeof(d));

    d[source] = ;

    q.push({, source});

    while(!q.empty())

    {

        pair<ll, int> o = q.top();

        q.pop();

        int u = o.second;

        if(vis[u]) continue;

        vis[u] = ;

        for(int i = hd[u]; i; i = e[i].nxt) if(d[e[i].to] > d[u] + e[i].w)

        {

            d[e[i].to] = d[u] + e[i].w;

            q.push({d[e[i].to], e[i].to});

        }

    }

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

    return ;

}