#include <cstdio>
#include <climits>
#include <queue>
#include <stack>

const int MAXN = 200000;
const int MAXM = 1000000;

int n, m;

struct Node;
struct Edge;
struct SCC;

struct Node {
    Edge *firstEdge, *currentEdge, *inEdge;
    SCC *scc;
    int dfn, low;
    bool inStack, visited, pushed;

	int d;
	bool q;
} nodes[MAXN];

struct Edge {
    Node *from, *to;
    Edge *next;
	int w;

    Edge(Node *from, Node *to, const int w) : from(from), to(to), next(from->firstEdge), w(w) {}
};

struct SCC {
    int size;
	Node v;
} sccs[MAXN];

inline void addEdge(const int u, const int v, const int w) {
	nodes[u].firstEdge = new Edge(&nodes[u], &nodes[v], w);
}

inline int tarjan() {
    int timeStamp = 0, count = 0;

    for (int i = 0; i < n; i++) {
        if (nodes[i].visited) continue;

        std::stack<Node *> s, t;
        s.push(&nodes[i]);
        nodes[i].pushed = true;

        while (!s.empty()) {
            Node *v = s.top();

            if (!v->visited) {
                v->visited = true;
                v->currentEdge = v->firstEdge;
                v->dfn = v->low = timeStamp++;
                v->inStack = true;
                t.push(v);
            }

            if (v->currentEdge) {
                Edge *&e = v->currentEdge;
                if (!e->to->pushed) s.push(e->to), e->to->pushed = true, e->to->inEdge = e;
                else if (e->to->inStack) v->low = std::min(v->low, e->to->dfn);
                e = e->next;
            } else {
                if (v->dfn == v->low) {
                    v->scc = &sccs[count++];
                    Node *u;
                    do {
                        u = t.top();
                        t.pop();
                        u->inStack = false;
                        u->scc = v->scc;
                        u->scc->size++;
                    } while (u != v);
                }

                if (v->inEdge) v->inEdge->from->low = std::min(v->inEdge->from->low, v->low);

                s.pop();
            }
        }
    }

    return count;
}

inline void contract() {
    for (int i = 0; i < n; i++) {
        for (Edge *e = nodes[i].firstEdge; e; e = e->next) {
            if (e->from->scc != e->to->scc) {
                Node *from = &e->from->scc->v, *to = &e->to->scc->v;
                from->firstEdge = new Edge(from, to, e->w);
            }
        }
    }
}

inline int bellmanford() {
	for (int i = 0; i < n; i++) nodes[i].scc->v.d = INT_MAX;

	std::queue<Node *> q;
	q.push(&nodes[0].scc->v);
	nodes[0].scc->v.d = 0;

	while (!q.empty()) {
		Node *v = q.front();
		q.pop();
		v->q = false;

		for (Edge *e = v->firstEdge; e; e = e->next) {
			if (e->to->d > v->d + e->w) {
				e->to->d = v->d + e->w;
				if (!e->to->q) e->to->q = true, q.push(e->to);
			}
		}
	}

	return nodes[n - 1].scc->v.d;
}

int main() {
	freopen("regexp.in", "r", stdin);
	freopen("regexp.out", "w", stdout);

	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w), u--, v--;
		addEdge(u, v, w);
	}

	tarjan();
	contract();
	printf("%d\n", bellmanford());

	fclose(stdin);
	fclose(stdout);

	return 0;
}