#ifndef __GRAPH_H__
#define __GRAPH_H__

/* updated: 2019-10-04 */

#include <cassert>
#include <vector>
#include <algorithm>
#include <limits>
#include <queue>
#include <functional>
#include <utility>
#include <stack>

/* vector<Edge> とその配列で名前変えたほうがいいかも */
/* 辺の重複、自己ループ、辺の削除(負の辺の判定含め) */
/* 辺の探索 */
/* 経路復元 */

using CostType = long long;

struct EdgeTC {
	int to;
	CostType cost;
	EdgeTC(int to, CostType cost);

	static int compareByCost(const EdgeTC& left, const EdgeTC& right);

	struct GreaterCost {
		bool operator()(const EdgeTC& left, const EdgeTC& right);
	};
};

struct EdgeFTC {
	int from;
	int to;
	CostType cost;
	EdgeFTC(int from, int to, CostType cost);

	static int compareByCost(const EdgeFTC& left, const EdgeFTC& right);

	struct GreaterCost {
		bool operator()(const EdgeFTC& left, const EdgeFTC& right);
	};
	struct LessCost {
		bool operator()(const EdgeFTC& left, const EdgeFTC& right);
	};
};


/* 多重辺、自己ループはない仕様 */
/* 頂点に何かが割り振られているときもあるよね */
class GraphAsListImpl {
public:
	using Edge = EdgeTC;
	using List = std::vector<Edge>;
	using Iterator = List::iterator;
	using ConstIterator = List::const_iterator;

protected:
	List* graph_p_m;
	int size_m;

	void Copy(const GraphAsListImpl& other);
	bool Is_valid_vertex(int vertex) const;

public:
	GraphAsListImpl();
	GraphAsListImpl(int size);
	GraphAsListImpl(const GraphAsListImpl& other);
	~GraphAsListImpl();

	GraphAsListImpl& operator=(const GraphAsListImpl& other);
	const List& operator[](int index) const;

	int size() const;
	void add(int from, int to, CostType cost, bool bidirected = false);
	Iterator find(int from, int to);
	ConstIterator find(int from, int to) const;
	bool erase(int from, int to);
};

class GraphAsListBidirected;
class GraphAsList {
public:
	using Edge = GraphAsListImpl::Edge;
	using List = GraphAsListImpl::List;
	using Iterator = GraphAsListImpl::Iterator;
	using ConstIterator = GraphAsListImpl::ConstIterator;

private:
	GraphAsListImpl graph_impl_m;

public:
	GraphAsList();
	GraphAsList(int size);
	GraphAsList(const GraphAsList& other);
	GraphAsList(const GraphAsListBidirected& other);
	~GraphAsList();

	GraphAsList& operator=(const GraphAsList& other);
	const List& operator[](int index) const;

	int size() const;
	void add(int from, int to, CostType cost = 1, bool bidirected = false);
	Iterator find(int from, int to);
	ConstIterator find(int from, int to) const;
	bool erase(int from, int to, bool bidirected = false);
};


class GraphAsListBidirected {
public:
	/* メンバ関数に対する friend は記述の順番に注意 */
	friend GraphAsList::GraphAsList(const GraphAsListBidirected& other);

	using Edge = GraphAsListImpl::Edge;
	using List = GraphAsListImpl::List;
	using Iterator = GraphAsListImpl::Iterator;
	using ConstIterator = GraphAsListImpl::ConstIterator;
private:
	GraphAsListImpl graph_impl_m;
public:
	GraphAsListBidirected();
	GraphAsListBidirected(int size);
	GraphAsListBidirected(const GraphAsListBidirected& other);
	~GraphAsListBidirected();

	GraphAsListBidirected& operator=(const GraphAsListBidirected& other);
	const List& operator[](int index) const;

	int size() const;
	void add(int vertex1, int vertex2, CostType cost = 1);
	std::pair<Iterator, Iterator> find(int vertex1, int vertex2);
	std::pair<ConstIterator, ConstIterator> find(int vertex1, int vertex2) const;
	bool erase(int vertex1, int vertex2);
};

/* 強連結成分分解 */
class SCCsCalculator {
	GraphAsList graph_m;

	int current_m;
	std::vector<int> index_m;
	std::vector<int> lowlink_m;
	std::vector<bool> on_stack_m;
	std::stack<int> stack_m;

	std::vector<std::vector<int>> SCCs_m;

	void calcSubRec(int from);
	void calcSub(int start);

	static const int Unvisited = -1;
public:
	SCCsCalculator(const GraphAsList& graph);
	std::vector<std::vector<int>> execute();
};

/* 連結性を仮定 */
class LowlinkCalculator {
public:
	using Edge = EdgeFTC;
private:
	GraphAsListBidirected graph_m;

	int current_m;
	std::vector<int> index_m;
	std::vector<int> lowlink_m;
	std::vector<int> parent_m;
	//Tree childs;

	void calcSubRec(int from, int parent);
	void calcSub(int start);

	static const int Unvisited = -1;

public:
	LowlinkCalculator(const GraphAsListBidirected& graph);
	void execute();
	std::vector<Edge> bridges();
	std::vector<int> articulations();
};

struct GraphQueueElement {
	CostType distance_m;
	int vertex_m;

	static int compare(const GraphQueueElement& left, const GraphQueueElement& right);

	GraphQueueElement(CostType distance, int vertex);
	GraphQueueElement(const GraphQueueElement&) = default;
};

bool operator<(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator>(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator<=(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator>=(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator==(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator!=(const GraphQueueElement& left, const GraphQueueElement& right);

std::vector<CostType> dijkstra(const GraphAsList& graph, int start);
GraphAsListBidirected prim(const GraphAsListBidirected& graph_arg);
GraphAsListBidirected kruskal(const GraphAsListBidirected& graph);

#endif
#pragma warning(disable:4996)
#if ONLY_MY_ENVIR
#include "Graph.h"
#include "UnionFind.h"
#endif

#include <queue>
#include <stdexcept>

/*-----------------------------------*/
/*------------   EdgeTC   -----------*/
/*-----------------------------------*/

EdgeTC::EdgeTC(int to, CostType cost)
	: to(to), cost(cost) {
}

int EdgeTC::compareByCost(const EdgeTC& left, const EdgeTC& right) {
	if (left.cost > right.cost) return 1;
	if (left.cost < right.cost) return -1;
	if (left.to > right.to) return 1;
	if (left.to < right.to) return -1;
	return 0;
}

bool EdgeTC::GreaterCost::operator()(const EdgeTC& left, const EdgeTC& right) {
	return compareByCost(left, right) > 0;
}

/*---------------------------------------*/
/*-------------   EdgeFTC   -------------*/
/*---------------------------------------*/

EdgeFTC::EdgeFTC(int from, int to, CostType cost)
	:from(from), to(to), cost(cost) {
}

int EdgeFTC::compareByCost(const EdgeFTC & left, const EdgeFTC & right) {
	if (left.cost > right.cost) return 1;
	if (left.cost < right.cost) return -1;
	if (left.from > right.from) return 1;
	if (left.from < right.from) return -1;
	if (left.to > right.to) return 1;
	if (left.to < right.to) return -1;
	return 0;
}

bool EdgeFTC::GreaterCost::operator()(const EdgeFTC & left, const EdgeFTC & right) {
	return compareByCost(left, right) > 0;
}

bool EdgeFTC::LessCost::operator()(const EdgeFTC & left, const EdgeFTC & right) {
	return compareByCost(left, right) < 0;
}


/*---------------------------------------*/
/*---------   GraphAsListImpl   ---------*/
/*---------------------------------------*/

void GraphAsListImpl::Copy(const GraphAsListImpl& other) {
	if (graph_p_m == other.graph_p_m) return;
	delete[] graph_p_m;
	size_m = other.size_m;
	graph_p_m = new List[size_m];
	std::copy(other.graph_p_m, other.graph_p_m + size_m, graph_p_m);
}

bool GraphAsListImpl::Is_valid_vertex(int vertex) const {
	return vertex >= 0 && vertex <= size_m;
}

GraphAsListImpl::GraphAsListImpl()
	:size_m(0), graph_p_m(nullptr) {
}

GraphAsListImpl::GraphAsListImpl(int size)
	: size_m(size) {
	graph_p_m = new List[size_m];
}

GraphAsListImpl::GraphAsListImpl(const GraphAsListImpl& other)
	: GraphAsListImpl() {
	Copy(other);
}

GraphAsListImpl::~GraphAsListImpl() {
	delete[] graph_p_m;
}

GraphAsListImpl& GraphAsListImpl::operator=(const GraphAsListImpl& other) {
	Copy(other);
	return *this;
}

const GraphAsListImpl::List& GraphAsListImpl::operator[](int index) const {
	return graph_p_m[index];
}

int GraphAsListImpl::size() const {
	return size_m;
}

void GraphAsListImpl::add(int from, int to, CostType cost, bool bidirected) {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	if (bidirected) {
		add(from, to, cost, false);
		add(to, from, cost, false);
		return;
	}
	graph_p_m[from].push_back(Edge(to, cost));
}

GraphAsListImpl::Iterator GraphAsListImpl::find(int from, int to) {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	List& list = graph_p_m[from];
	for (auto it = list.begin(); it != list.end(); ++it) {
		if (it->to == to) return it;
	}
	return list.end();
}

GraphAsListImpl::ConstIterator GraphAsListImpl::find(int from, int to) const {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	List& list = graph_p_m[from];
	for (auto it = list.begin(); it != list.end(); ++it) {
		if (it->to == to) return it;
	}
	return list.end();
}

bool GraphAsListImpl::erase(int from, int to) {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	List& list = graph_p_m[from];
	auto it = find(from, to);
	if (it == graph_p_m[from].end()) return false;
	list.erase(it);
	return true;
}

/*---------------------------*/
/*-----   GraphAsList   -----*/
/*---------------------------*/

GraphAsList::GraphAsList() : graph_impl_m() {}
GraphAsList::GraphAsList(int size) : graph_impl_m(size) {}
GraphAsList::GraphAsList(const GraphAsList& other) : graph_impl_m(other.graph_impl_m) {}
GraphAsList::GraphAsList(const GraphAsListBidirected& other) : graph_impl_m(other.graph_impl_m) {}
GraphAsList::~GraphAsList() {}
GraphAsList& GraphAsList::operator=(const GraphAsList& other) {
	graph_impl_m = other.graph_impl_m;
	return *this;
}

const GraphAsList::List& GraphAsList::operator[](int index) const {
	return graph_impl_m[index];
}

int GraphAsList::size() const {
	return graph_impl_m.size();
}

void GraphAsList::add(int from, int to, CostType cost, bool bidirected) {
	graph_impl_m.add(from, to, cost, bidirected);
}

GraphAsList::Iterator GraphAsList::find(int from, int to) {
	return graph_impl_m.find(from, to);
}

GraphAsList::ConstIterator GraphAsList::find(int from, int to) const {
	return graph_impl_m.find(from, to);
}

bool GraphAsList::erase(int from, int to, bool bidirected) {
	if (bidirected) graph_impl_m.erase(from, to) && graph_impl_m.erase(to, from);
	return graph_impl_m.erase(from, to);
}

/*-------------------------------------*/
/*-----   GraphAsListBidirected   -----*/
/*-------------------------------------*/

GraphAsListBidirected::GraphAsListBidirected() : graph_impl_m() {}
GraphAsListBidirected::GraphAsListBidirected(int size) : graph_impl_m(size) {}
GraphAsListBidirected::GraphAsListBidirected(const GraphAsListBidirected& other) : graph_impl_m(other.graph_impl_m) {}
GraphAsListBidirected::~GraphAsListBidirected() {}

GraphAsListBidirected& GraphAsListBidirected::operator=(const GraphAsListBidirected& other) {
	graph_impl_m = other.graph_impl_m;
	return *this;
}

const GraphAsListBidirected::List& GraphAsListBidirected::operator[](int index) const {
	return graph_impl_m[index];
}

int GraphAsListBidirected::size() const {
	return graph_impl_m.size();
}

void GraphAsListBidirected::add(int vertex1, int vertex2, CostType cost) {
	return graph_impl_m.add(vertex1, vertex2, cost, true);
}

std::pair<GraphAsListBidirected::Iterator, GraphAsListBidirected::Iterator>
GraphAsListBidirected::find(int vertex1, int vertex2) {
	return make_pair(graph_impl_m.find(vertex1, vertex2), graph_impl_m.find(vertex2, vertex1));
}

std::pair<GraphAsListBidirected::ConstIterator, GraphAsListBidirected::ConstIterator>
GraphAsListBidirected::find(int vertex1, int vertex2) const {
	return make_pair(graph_impl_m.find(vertex1, vertex2), graph_impl_m.find(vertex2, vertex1));
}

bool GraphAsListBidirected::erase(int vertex1, int vertex2) {
	return graph_impl_m.erase(vertex1, vertex2) && graph_impl_m.erase(vertex2, vertex1);
}

/*--------------------------------------*/
/*---------   SCCsCalculator   ---------*/
/*--------------------------------------*/

void SCCsCalculator::calcSubRec(int from) {
	index_m[from] = current_m;
	lowlink_m[from] = current_m;
	++current_m;
	stack_m.push(from);
	on_stack_m[from] = true;

	for (auto&& edge : graph_m[from]) {
		int to = edge.to;
		if (index_m[to] == Unvisited) {
			calcSubRec(to);
			lowlink_m[from] = std::min(lowlink_m[from], lowlink_m[to]);
		} else if (on_stack_m[to]) {		// この条件何のため？
			lowlink_m[from] = std::min(lowlink_m[from], index_m[to]);
		}
	}

	if (lowlink_m[from] == index_m[from]) {
		SCCs_m.push_back(std::vector<int>());
		int vertex;
		do {
			vertex = stack_m.top();
			stack_m.pop();

			on_stack_m[vertex] = false;
			SCCs_m.back().push_back(vertex);
		} while (vertex != from);
	}
}

void SCCsCalculator::calcSub(int start) {
	calcSubRec(start);
}

SCCsCalculator::SCCsCalculator(const GraphAsList& graph)
	: graph_m(graph), current_m(0), index_m(graph.size(), Unvisited),
	lowlink_m(graph.size(), Unvisited), on_stack_m(graph.size(), false) {
}

std::vector<std::vector<int>> SCCsCalculator::execute() {
	const int size = graph_m.size();
	for (int i = 0; i < size; ++i) {
		if (index_m[i] != Unvisited) continue;
		calcSub(i);
	}
	return SCCs_m;
}

/*-----------------------------------------*/
/*---------   LowlinkCalculator   ---------*/
/*-----------------------------------------*/

void LowlinkCalculator::calcSubRec(int from, int parent) {
	index_m[from] = current_m;
	lowlink_m[from] = current_m;
	++current_m;

	for (auto&& edge : graph_m[from]) {
		int to = edge.to;
		if (to == parent) continue;

		if (index_m[to] == Unvisited) {
			calcSubRec(to, from);
			lowlink_m[from] = std::min(lowlink_m[from], lowlink_m[to]);
			parent_m[to] = from;
		} else {
			lowlink_m[from] = std::min(lowlink_m[from], index_m[to]);
		}
	}
}

void LowlinkCalculator::calcSub(int start) {
	parent_m[start] = start;
	calcSubRec(start, -1);
}

LowlinkCalculator::LowlinkCalculator(const GraphAsListBidirected& graph)
	: graph_m(graph), current_m(0), index_m(graph.size(), Unvisited), lowlink_m(graph.size(), Unvisited), parent_m(graph.size()) {
}

void LowlinkCalculator::execute() {
	const int size = graph_m.size();
	for (int i = 0; i < size; ++i) {
		if (index_m[i] != Unvisited) continue;
		calcSub(i);
	}
}

std::vector<LowlinkCalculator::Edge> LowlinkCalculator::bridges() {
	const int size = graph_m.size();
	std::vector<Edge> ret_vec;
	for (int i = 0; i < size; ++i) {
		int parent = parent_m[i];
		if (parent == i) continue;
		if (lowlink_m[i] > index_m[parent]) {
			int vertex1 = std::min(i, parent);
			int vertex2 = std::max(i, parent);
			ret_vec.push_back(Edge(vertex1, vertex2, 1));
		}
	}
	return ret_vec;
}

std::vector<int> LowlinkCalculator::articulations() {
	return std::vector<int>();
}



/*----------------------------------*/
/*---------   グローバル   ---------*/
/*----------------------------------*/

int GraphQueueElement::compare(const GraphQueueElement& left, const GraphQueueElement& right) {
	if (left.distance_m > right.distance_m) return 1;
	if (left.distance_m < right.distance_m) return -1;
	return 0;
}

GraphQueueElement::GraphQueueElement(CostType distance, int vertex)
	: distance_m(distance), vertex_m(vertex) {
}

bool operator<(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::compare(left, right) < 0;
}

bool operator>(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::compare(left, right) > 0;
}

bool operator<=(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::compare(left, right) <= 0;
}

bool operator>=(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::compare(left, right) >= 0;
}

bool operator==(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::compare(left, right) == 0;
}

bool operator!=(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::compare(left, right) != 0;
}

std::vector<CostType> dijkstra(const GraphAsList& graph, int start) {
	// assert(!Has_negative_edge());

	using Elem = GraphQueueElement;

	const int size = graph.size();
	const CostType INF_DIST = std::numeric_limits<CostType>::max();
	std::priority_queue<Elem, std::vector<Elem>, std::greater<Elem> > que;

	std::vector<CostType> dist_arr(size, INF_DIST);
	dist_arr[start] = 0;
	que.push(Elem(0, start));

	while (!que.empty()) {
		const Elem curr_pair = que.top();
		que.pop();

		const CostType curr_dist = curr_pair.distance_m;
		const int from = curr_pair.vertex_m;

		if (curr_dist > dist_arr[from]) continue;

		for (auto&& elem : graph[from]) {
			const int to = elem.to;
			const CostType cost = elem.cost;
			const CostType new_dist = curr_dist + cost;

			if (new_dist >= dist_arr[to]) continue;
			dist_arr[to] = new_dist;
			que.push(Elem(new_dist, to));
		}
	}
	return dist_arr;
}


/* 無向グラフとみなしてプリム O(ElogE) */
GraphAsListBidirected prim(const GraphAsListBidirected& graph_arg) {
	using Edge = EdgeFTC;

	const GraphAsList graph(graph_arg);
	const int size = graph.size();
	bool* used_p = new bool[size];
	std::fill(used_p, used_p + size, false);
	std::priority_queue<Edge, std::vector<Edge>, Edge::GreaterCost> edge_queue;
	
	int start = 0;
	used_p[start] = true;
	for (auto&& edge : graph[start]) {
		edge_queue.push(Edge(start, edge.to, edge.cost));
	}

	int edge_count = 0;
	GraphAsListBidirected ret_graph(size);
	while (edge_count < size - 1) {
		if (edge_queue.empty()) throw std::runtime_error("graph must be connected");
		Edge edge = edge_queue.top(); edge_queue.pop();
		int from = edge.from;
		int to = edge.to;
		CostType cost = edge.cost;
		if (used_p[to]) continue;

		used_p[to] = true;
		ret_graph.add(from, to, cost);
		for (auto&& new_edge : graph[to]) {
			if (used_p[new_edge.to]) continue;
			edge_queue.push(Edge(to, new_edge.to, new_edge.cost));
		}
		++edge_count;
	}
	delete[] used_p;
	return ret_graph;
}

/* 無向グラフとみなしてクラスカル O(ElogE) */
GraphAsListBidirected kruskal(const GraphAsListBidirected& graph) {
#ifdef __UNION_FIND_H__
	using Edge = EdgeFTC;

	int size = graph.size();
	UnionFindTree union_find(size);
	std::vector<Edge> edge_arr;

	for (int from = 0; from < size; ++from) {
		for (auto&& edge : graph[from]) {
			if (from > edge.to) continue;
			edge_arr.push_back(Edge(from, edge.to, edge.cost));
		}
	}
	std::sort(edge_arr.begin(), edge_arr.end(), Edge::LessCost());

	GraphAsListBidirected ret_graph(size);
	int edge_count = 0;
	for(auto&& edge : edge_arr) {
		if (edge_count == size - 1) break;
		int from = edge.from;
		int to = edge.to;
		CostType cost = edge.cost;
		if (union_find.isSame(from, to)) continue;
		ret_graph.add(from, to, cost);
		union_find.unite(from, to);
		++edge_count;
	}
	return ret_graph;
#else
#endif
}

#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>

using namespace std;
using uint = uint32_t;
using LL = int64_t;
using ULL = uint64_t;
using PP = pair<LL, LL>;
template <typename T> using PriorityQ = priority_queue<T, vector<T>, greater<T> >;
#define REP(i, a, n) for(LL i = (a), i##_max_ = (n); i < i##_max_; ++i)
#define REM(i, a, n) for(LL i = (LL)(n) - 1, i##_min_ = (a); i >= i##_min_; --i)
#define FLOAT fixed << setprecision(16)
#define SPEEDUP { cin.tie(NULL); ios::sync_with_stdio(false); }
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const double EPS = 1.0e-9;

void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U> istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U> ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N> void Fill(T(&dest)[N], const TCompatible& val) { fill(dest, dest + N, val); }
template <class T, class TCompatible, size_t M, size_t N> void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template <class T> T Next() { T buf; cin >> buf; return buf; }
istream& Ignore(istream& ist) { string s; ist >> s; return ist; }
bool Inside(int i, int j, int h, int w) { return i >= 0 && i < h && j >= 0 && j < w; }

#ifdef ONLY_MY_ENVIR
#include "IntMod.h"
#include "Algebraic.h"
#include "BinaryMatrix.h"
#include "BinaryTree.h"
#include "Bipartite.h"
#include "BIT.h"
#include "DynamicMod.h"
#include "Factorization.h"
#include "FFT.h"
#include "FlowSolver.h"
#include "Graph.h"
#include "LazySegmentTree.h"
#include "Math.h"
#include "Matrix.h"
#include "MinCostFlowSolver.h"
#include "MinMax.h"
#include "Numbers.h"
#include "Polynomial.h"
#include "Position.h"
#include "Range.h"
#include "Rational.h"
#include "SegmentTree.h"
#include "SegmentTree2D.h"
#include "SuffixArray.h"
#include "Tree.h"
#include "UnionFind.h"
#endif

#ifdef __GNUC__
typedef __int128 LLL;
istream& operator>> (istream& ist, __int128& val) { LL tmp; ist >> tmp; val = tmp; return ist; }
ostream& operator<< (ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#endif

int N, M;
int main() {
	cin >> N >> M;
	GraphAsList G(N);
	REP(i, 1, N) {
		G.add(i, i - 1, 0);
	}

	REP(j, 0, M) {
		int a, b, c;
		cin >> a >> b >> c;
		--a; --b;
		G.add(a, b, c);
	}

	auto d = dijkstra(G, 0);
	LL ans = d[N - 1];

	cout << (ans >= 1e18 ? -1 : ans) << endl;
	return 0;
}


Measured memory_bytes: 10104