#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <queue>
#include <algorithm>
#include <functional>
#include <set>

using namespace std;

vector<vector<pair<int,int>>> g;

void read()
{
	ifstream in("dijkstra.in");
	int n, m;
	in >> n >> m;
	g.resize(n, {});
	for(int i = 0; i < m; ++i)
	{
		int u, v, cost;
		in >> u >> v >> cost;
		g[u-1].emplace_back(v-1, cost);
	}
}

template<typename T>
class update_key_priority_queue
{
	set<pair<T, int>> s;
	vector<int> id_map;

public:
	update_key_priority_queue(int n_keys) : id_map(n_keys) {}

	update_key_priority_queue(const vector<pair<int, T>> &data)
	{
		id_map.resize(data.size());
		for(const auto &item : data)
		{
			id_map[item.first] = item.second;
			s.emplace(item.second, item.first);
		}
	}

	void insert(int key, T priority)
	{
		id_map[key] = priority;
		s.insert(make_pair(priority, key));
	}

	pair<int, T> top()
	{
		auto i = s.begin();
		return make_pair(i->second, i->first);
	}

	void pop()
	{
		s.erase(s.begin());
	}

	bool contains(int key)
	{
		if( key >= id_map.size() && key < 0)
			return false;
		return (s.count(make_pair(id_map[key], key)) != 0);
	}

	void update_key(int key, T new_value)
	{
		T &current_value = id_map[key];
		pair<T, int> v{current_value, key};
		if(s.count(v) != 0)
		{
			s.erase(v);
		}
		s.insert(make_pair(new_value, key));
		id_map[key] = new_value;
	}


	bool empty()
	{
		return s.empty();
	}

	void ps(set<pair<T, int>> s)
	{
		for(auto &v : s)
		{
			cout << "(" << v.first << " " << v.second << ") ";
		}
		cout << endl;
	}

	void d_print()
	{
		for(auto &v : id_map)
			cout << v << " ";
		cout << endl;
		ps(s);
	}
};

void test_pq()
{
	vector<pair<int, int>> data{
		{1, 20}, {2, 40}, {4, 5}, {0, 15}, {3, 25}
	};
	cout << "test_pq" << endl;
	update_key_priority_queue<int> pq(data.size());
	for(auto &v : data)
	{
		pq.insert(v.first, v.second);
	}
	//pq.update_key(1, 2);
	pq.d_print();
	cout << "test_pq_end" << endl;
}

void new_compute_distance(int src)
{
	vector<int> dist(g.size(), INT_MAX);
	dist[src] = 0;

	update_key_priority_queue<int> pq(g.size());
	for(int i = 0; i < (int)g.size(); ++i)
	{
		pq.insert(i, dist[i]);
	}

	int cnt = 0;
	
	while(!pq.empty())
	{
		int u = pq.top().first;
		int d = pq.top().second;
		pq.pop();
		if(d == INT_MAX)
			break;
		for(auto &n : g[u])
		{
			++cnt;
			int v = n.first;
			int d_v = n.second;
			int new_d = d + d_v;
			if(new_d < dist[v])
			{
				dist[v] = new_d;
				pq.update_key(v, new_d);
			}
		}
	}
	cout << cnt << endl;
	ofstream out("dijkstra.out");
	for_each(begin(dist) + 1, end(dist), [&out](int &d) { 
		if(d == INT_MAX) d = 0;
		out << d << " ";
	});
	out << endl;
}

void compute_distance(int src)
{
	vector<int> dist(g.size(), INT_MAX);
	dist[src] = 0;

	auto comp = [](pair<int, int> &a, pair<int, int> &b) { 
		return a.second > b.second; 
	};
	priority_queue< 
		pair<int, int>,
		vector<pair<int, int>>,
		decltype(comp)
	> pq(comp);

	for(int i = 0; i < g.size(); ++i)
		pq.emplace(i, dist[i]);

	int cnt = 0;
	while(!pq.empty())
	{
		int u = pq.top().first;
		int d = pq.top().second;
		pq.pop();
		if(d == INT_MAX)
			break;
		for(auto &n : g[u])
		{
			++cnt;
			int v = n.first;
			int d_v = n.second;
			int new_d = d + d_v;
			if(new_d < dist[v])
			{
				dist[v] = new_d;
				pq.emplace(v, new_d);
			}
		}
	}
	cout << cnt << endl;
	ofstream out("dijkstra.out");
	for_each(begin(dist) + 1, end(dist), [&out](int &d) { 
		if(d == INT_MAX) d = 0;
		out << d << " ";
	});
	out << endl;
}

int main()
{
	read();
	cout << "read" << endl;
	new_compute_distance(0);
	//compute_distance(0);
	return 0;
}