#include <bits/stdc++.h>
class Graph
{
public:
using neighbour_t = std::pair<int, int>;
public:
Graph() = default;
Graph(const std::size_t nr_noduri, const std::vector<std::vector<int>>& l_in)
: nr_noduri(nr_noduri)
{
l_adiacenta.resize(nr_noduri + 1);
for(std::size_t i = 0; i < l_in.size(); ++i)
{
for(std::size_t j = 0; j < l_in[i].size(); ++j)
{
l_adiacenta[i].push_back({l_in[i][j], 0});
}
}
}
void add_edge(const int u, const int v, const int w = 0)
{
l_adiacenta[u].push_back({v, w});
}
void set_nr_noduri(const std::size_t n)
{
nr_noduri = n;
l_adiacenta.resize(n);
}
int componente_conexe() const;
std::vector<int> distante_minime(const int start) const;
std::vector<int> sortare_topologica() const;
std::vector<int> grade_interne() const;
std::vector<std::vector<int>> comp_tare_conexe() const;
std::vector<std::vector<int>> comp_biconexe() const;
std::vector<std::pair<int, int>> muchii_critice() const;
static std::vector<int> ciclu_euler(const int N,
const std::vector<std::pair<int, int>>& muchii);
static int disjoint_set_find(const std::vector<int>& link, int x);
static void disjoint_set_unite(std::vector<int>& link, std::vector<int>& size, int a,
int b);
static bool hakimi(std::vector<int>);
protected:
void DFS(std::vector<bool>& visited, int src) const;
void DFS_ordine(std::vector<unsigned char>& visited, std::vector<int>& res,
const int src) const;
void BFS(std::vector<int>& dists, int start) const;
void ctc(const int src, int& idx, std::vector<int>& indexes,
std::vector<int>& low_link, std::vector<unsigned char>& on_stack,
std::stack<int>& stack, std::vector<std::vector<int>>& res) const;
void DFS_biconexe(const int, const int, const int, std::vector<int>&,
std::vector<int>&, std::stack<std::pair<int, int>>&,
std::vector<std::vector<int>>&) const;
void DFS_muchii_critice(const int, const int, const int, std::vector<int>&,
std::vector<int>&, std::stack<std::pair<int, int>>&,
std::vector<std::pair<int, int>>&) const;
protected:
std::size_t nr_noduri;
std::vector<std::vector<neighbour_t>> l_adiacenta;
};
class WeightedGraph : public Graph
{
public:
WeightedGraph(const std::size_t n,
std::vector<std::vector<std::pair<int, int>>>&& l_in)
{
nr_noduri = n;
l_adiacenta = std::move(l_in);
}
std::vector<std::array<int, 3>> cost_apm() const;
std::vector<int> distante_minime_dijkstra(const int src) const;
std::vector<std::vector<int>> distante_minime_floyd() const;
std::pair<bool, std::vector<int>> distante_minime_bellmanford(const int src) const;
int maxflow(const int src, const int dest) const;
int cost_ciclu_hamilton_minim() const;
private:
std::vector<std::vector<neighbour_t>>& adj = l_adiacenta;
};
int Graph::componente_conexe() const
{
std::vector<bool> visited(nr_noduri + 1, false);
int res = 0;
for(int node = 1; node <= (int)nr_noduri; ++node)
{
if(!visited[node])
{
++res;
DFS(visited, node);
}
}
return res;
}
std::vector<int> Graph::distante_minime(const int start) const
{
std::vector<int> distante(nr_noduri + 1, -1);
BFS(distante, start);
return distante;
}
std::vector<int> Graph::sortare_topologica() const
{
std::vector<int> sorted;
const auto grd_i = grade_interne();
std::vector<unsigned char> viz(nr_noduri + 1, false);
for(std::size_t node = 1; node <= nr_noduri; ++node)
{
if(grd_i[node] == 0 && !viz[node])
{
DFS_ordine(viz, sorted, node);
}
}
std::reverse(sorted.begin(), sorted.end());
return sorted;
}
std::vector<int> Graph::grade_interne() const
{
std::vector<int> res(nr_noduri + 1, 0);
for(auto& l : l_adiacenta)
{
for(const auto& edge : l)
{
const int v = edge.first;
++res[v];
}
}
return res;
}
void Graph::DFS(std::vector<bool>& visited, int start) const
{
visited[start] = true;
for(const auto& edge : l_adiacenta[start])
{
const int v = edge.first;
if(!visited[v])
{
DFS(visited, v);
}
}
}
void Graph::DFS_ordine(std::vector<unsigned char>& visited, std::vector<int>& res,
const int src) const
{
visited[src] = true;
for(const auto& edge : l_adiacenta[src])
{
const int v = edge.first;
if(!visited[v])
{
DFS_ordine(visited, res, v);
}
}
res.push_back(src);
}
void Graph::BFS(std::vector<int>& dists, int start) const
{
std::queue<int> q;
q.push(start);
dists[start] = 0;
while(!q.empty())
{
const auto node = q.front();
q.pop();
for(const auto& edge : l_adiacenta[node])
{
const int v = edge.first;
if(dists[v] == -1)
{
q.push(v);
dists[v] = dists[node] + 1;
}
}
}
}
bool Graph::hakimi(std::vector<int> degrees)
{
if(degrees.empty())
{
return true;
}
while(true)
{
if(std::any_of(degrees.begin(), degrees.end(),
[](const int deg)
{
return deg < 0;
}))
{
return false;
}
std::sort(degrees.begin(), degrees.end());
if(degrees.back() == 0)
{
return true;
}
const int current_deg = degrees.back();
degrees.pop_back();
if(static_cast<std::size_t>(current_deg) > degrees.size())
{
return false;
}
for(auto it = degrees.rbegin(); it != degrees.rbegin() + current_deg; ++it)
{
--(*it);
}
}
}
std::vector<std::vector<int>> Graph::comp_tare_conexe() const
{
std::vector<std::vector<int>> res;
int idx = 0;
std::stack<int> stack;
std::vector<int> indexes(nr_noduri + 1, -1);
std::vector<unsigned char> on_stack(nr_noduri + 1, false);
std::vector<int> low_link(nr_noduri + 1);
for(int node = 1; node <= (int)nr_noduri; ++node)
{
if(indexes[node] == -1)
{
ctc(node, idx, indexes, low_link, on_stack, stack, res);
}
}
return res;
}
void Graph::ctc(const int src, int& idx, std::vector<int>& indexes, std::vector<int>& low_link,
std::vector<unsigned char>& on_stack, std::stack<int>& stack,
std::vector<std::vector<int>>& res) const
{
indexes[src] = idx;
low_link[src] = idx;
++idx;
stack.push(src);
on_stack[src] = true;
for(const auto& edge : l_adiacenta[src])
{
const int neigh = edge.first;
if(indexes[neigh] == -1)
{
ctc(neigh, idx, indexes, low_link, on_stack, stack, res);
low_link[src] = std::min(low_link[src], low_link[neigh]);
}
else if(on_stack[neigh])
{
low_link[src] = std::min(low_link[src], indexes[neigh]);
}
}
if(low_link[src] == indexes[src])
{
int w;
std::vector<int> partial_res;
do
{
w = stack.top();
stack.pop();
on_stack[w] = false;
partial_res.push_back(w);
} while(src != w);
res.emplace_back(std::move(partial_res));
}
}
std::vector<std::vector<int>> Graph::comp_biconexe() const
{
std::vector<int> depths(nr_noduri + 1, -1);
std::vector<int> lowest_reachable_depth(nr_noduri + 1, INT_MAX);
std::stack<std::pair<int, int>> stack_muchii;
std::vector<std::vector<int>> res;
DFS_biconexe(1, 0, 0, depths, lowest_reachable_depth, stack_muchii, res);
for(auto& comp : res)
{
std::sort(comp.begin(), comp.end());
}
for(auto& comp : res)
{
comp.resize(std::unique(comp.begin(), comp.end()) - comp.begin());
}
return res;
}
void Graph::DFS_biconexe(const int src, const int parent, const int current_depth,
std::vector<int>& depths, std::vector<int>& lowest_reachable_depth,
std::stack<std::pair<int, int>>& stack_muchii,
std::vector<std::vector<int>>& res) const
{
depths[src] = current_depth;
lowest_reachable_depth[src] = current_depth;
for(const auto& edge : l_adiacenta[src])
{
const int neigh = edge.first;
if(depths[neigh] == -1 && neigh != parent)
{
stack_muchii.push(std::make_pair(src, neigh));
DFS_biconexe(neigh, src, current_depth + 1, depths,
lowest_reachable_depth, stack_muchii, res);
lowest_reachable_depth[src] = std::min(lowest_reachable_depth[src],
lowest_reachable_depth[neigh]);
if(lowest_reachable_depth[neigh] >= depths[src])
{
std::vector<int> component;
int muchie_x;
int muchie_y;
do
{
muchie_x = stack_muchii.top().first;
muchie_y = stack_muchii.top().second;
component.push_back(muchie_x);
component.push_back(muchie_y);
stack_muchii.pop();
} while(!(muchie_x == src && muchie_y == neigh));
res.emplace_back(std::move(component));
}
}
else if(neigh != parent)
{
lowest_reachable_depth[src] =
std::min(lowest_reachable_depth[src], depths[neigh]);
}
}
}
std::vector<std::pair<int, int>> Graph::muchii_critice() const
{
std::vector<int> depths(nr_noduri + 1, -1);
std::vector<int> lowest_reachable_depth(nr_noduri + 1, INT_MAX);
std::stack<std::pair<int, int>> stack_muchii;
std::vector<std::pair<int, int>> res;
DFS_muchii_critice(1, 0, 0, depths, lowest_reachable_depth, stack_muchii, res);
return res;
}
std::vector<int> Graph::ciclu_euler(const int N,
const std::vector<std::pair<int, int>>& muchii)
{
std::vector<std::vector<int>> adj_muchii(N + 1);
for(int i = 0; i < (int)muchii.size(); ++i)
{
const auto m = muchii[i];
adj_muchii[m.first].push_back(i);
adj_muchii[m.second].push_back(i);
}
for(int node = 1; node <= N; ++node)
{
if(adj_muchii[node].size() % 2 == 1)
{
return std::vector<int>{};
}
}
std::vector<int> ciclu;
std::stack<int> s;
std::unordered_set<int> used;
s.push(1);
while(!s.empty())
{
const int current = s.top();
if(!adj_muchii[current].empty())
{
const auto m = adj_muchii[current].back();
adj_muchii[current].pop_back();
if(used.find(m) == used.cend())
{
used.insert(m);
const int neigh =
muchii[m].first xor muchii[m].second xor current;
s.push(neigh);
}
}
else
{
s.pop();
ciclu.push_back(current);
}
}
return ciclu;
}
void Graph::DFS_muchii_critice(const int src, const int parent, const int current_depth,
std::vector<int>& depths,
std::vector<int>& lowest_reachable_depth,
std::stack<std::pair<int, int>>& stack_muchii,
std::vector<std::pair<int, int>>& res) const
{
depths[src] = current_depth;
lowest_reachable_depth[src] = current_depth;
for(const auto& edge : l_adiacenta[src])
{
const int neigh = edge.first;
if(depths[neigh] == -1 && neigh != parent)
{
stack_muchii.push(std::make_pair(src, neigh));
DFS_muchii_critice(neigh, src, current_depth + 1, depths,
lowest_reachable_depth, stack_muchii, res);
lowest_reachable_depth[src] = std::min(lowest_reachable_depth[src],
lowest_reachable_depth[neigh]);
if(lowest_reachable_depth[neigh] > depths[src])
{
res.emplace_back(std::make_pair(neigh, src));
}
}
else if(neigh != parent)
{
lowest_reachable_depth[src] =
std::min(lowest_reachable_depth[src], depths[neigh]);
}
}
}
int Graph::disjoint_set_find(const std::vector<int>& link, int x)
{
while(x != link[x])
{
x = link[x];
}
return x;
}
void Graph::disjoint_set_unite(std::vector<int>& link, std::vector<int>& size, int a, int b)
{
a = disjoint_set_find(link, a);
b = disjoint_set_find(link, b);
if(size[a] < size[b])
{
std::swap(a, b);
}
size[a] += size[b];
link[b] = a;
}
std::vector<std::array<int, 3>> WeightedGraph::cost_apm() const
{
std::vector<std::array<int, 3>> edges;
for(std::size_t node = 1; node <= nr_noduri; ++node)
{
for(auto& e : adj[node])
{
edges.push_back({(int)node, e.first, e.second});
}
}
std::sort(edges.begin(), edges.end(),
[](const auto& e1, const auto& e2)
{
return e1[2] < e2[2];
});
int n = nr_noduri;
std::vector<int> link(n + 1);
for(int i = 1; i <= n; ++i)
{
link[i] = i;
}
std::vector<int> size(n + 1, 1);
const auto find_set = [&](int x)
{
while(x != link[x])
{
x = link[x];
}
return x;
};
const auto unite = [&](int a, int b)
{
a = find_set(a);
b = find_set(b);
if(size[a] < size[b])
{
std::swap(a, b);
}
size[a] += size[b];
link[b] = a;
};
std::vector<const std::array<int, 3>*> idx;
for(const auto& edge : edges)
{
if(find_set(edge[0]) != find_set(edge[1]))
{
unite(find_set(edge[0]), find_set(edge[1]));
idx.push_back(&edge);
}
}
std::vector<std::array<int, 3>> res;
for(auto* ptr : idx)
{
res.push_back(*ptr);
}
return res;
}
std::vector<int> WeightedGraph::distante_minime_dijkstra(const int src) const
{
const int n = nr_noduri;
std::vector<char> visited(n + 1, false);
std::vector<int> distance(n + 1, INT_MAX);
distance[src] = 0;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
std::greater<std::pair<int, int>>>
q;
q.push({0, src});
while(!q.empty())
{
const std::pair<int,int> pair = q.top();
const int a = pair.second;
q.pop();
if(visited[a])
{
continue;
}
visited[a] = true;
for(auto& e : adj[a])
{
const int b = e.first;
const int w = e.second;
if(pair.first + w < distance[b])
{
distance[b] = pair.first + w;
q.push({distance[b], b});
}
}
}
return distance;
}
std::pair<bool, std::vector<int>>
WeightedGraph::distante_minime_bellmanford(const int src) const
{
const int n = nr_noduri;
std::vector<int> distance(n + 1, INT_MAX);
std::vector<int> times_in_queue(n + 1, 0);
std::queue<int> q;
std::vector<char> in_queue(n + 1, false);
bool has_negative_cycle = false;
distance[src] = 0;
q.push(src);
in_queue[src] = true;
while(!q.empty() && !has_negative_cycle)
{
const auto a = q.front();
q.pop();
in_queue[a] = false;
for(auto& e : adj[a])
{
const int b = e.first;
const int w = e.second;
if(distance[a] + w < distance[b])
{
distance[b] = distance[a] + w;
if(!in_queue[b])
{
if(times_in_queue[b] > n)
{
has_negative_cycle = true;
}
else
{
q.push(b);
in_queue[b] = true;
++times_in_queue[b];
}
}
}
}
}
return {has_negative_cycle, std::move(distance)};
}
std::vector<std::vector<int>> WeightedGraph::distante_minime_floyd() const
{
std::vector<std::vector<int>> dist(nr_noduri + 1,
std::vector<int>(nr_noduri + 1, INT_MAX));
for(std::size_t node = 1; node <= nr_noduri; ++node)
{
for(auto& e : adj[node])
{
dist[node][e.first] = e.second;
}
}
for(std::size_t node = 1; node <= nr_noduri; ++node)
{
dist[node][node] = 0;
}
for(std::size_t k = 1; k <= nr_noduri; ++k)
{
for(std::size_t i = 1; i <= nr_noduri; ++i)
{
for(std::size_t j = 1; j <= nr_noduri; ++j)
{
if(dist[i][k] == INT_MAX || dist[k][j] == INT_MAX)
{
continue;
}
if(dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
int WeightedGraph::cost_ciclu_hamilton_minim() const
{
const int INF = 1 << 27;
const int N = nr_noduri;
std::vector<std::vector<int>> dp(1 << (N), std::vector<int>(N, INF));
std::vector<std::vector<int>> cost(N, std::vector<int>(N, INF));
for(int node = 0; node < N; ++node)
{
for(auto& e : adj[node])
{
cost[e.first][node] = e.second;
}
}
dp[1][0] = 0;
for(int i = 0; i < 1 << N; ++i)
{
for(int j = 0; j < N; ++j)
{
if(!(i & (1 << j)))
{
continue;
}
for(auto& neigh : adj[j])
{
int k = neigh.first;
if(!(i & (1 << k)))
{
continue;
}
dp[i][j] =
std::min(dp[i][j], dp[i xor (1 << j)][k] + cost[k][j]);
}
}
}
int res = INF;
for(auto& e : adj[0])
{
int k = e.first;
res = std::min(res, dp[(1 << N) - 1][k] + cost[k][0]);
}
if(res == INF)
{
return INT_MAX;
}
return res;
}
int WeightedGraph::maxflow(const int src, const int dest) const
{
const std::size_t N = nr_noduri;
std::vector<std::vector<int>> capacity(N + 1, std::vector<int>(N + 1, 0));
std::vector<std::vector<int>> flow(N + 1, std::vector<int>(N + 1, 0));
for(std::size_t node = 1; node <= N; ++node)
{
for(const auto& e : adj[node])
{
capacity[node][e.first] = std::max(capacity[node][e.first], e.second);
}
}
const auto bfs_parents = [&]() -> std::vector<int>
{
std::vector<char> visited(N + 1, false);
std::vector<int> parent(N + 1, -1);
std::queue<int> q;
q.push(src);
visited[src] = true;
while(!q.empty())
{
const auto current = q.front();
q.pop();
for(const auto& neigh : adj[current])
{
if(visited[neigh.first] || capacity[current][neigh.first] <=
flow[current][neigh.first])
{
continue;
}
if(neigh.first == dest)
{
parent[dest] = current;
return parent;
}
q.push(neigh.first);
parent[neigh.first] = current;
visited[neigh.first] = true;
}
}
return parent;
};
int max_flow = 0;
while(true)
{
const auto parent = bfs_parents();
if(parent[dest] == -1)
{
break;
}
int path_min_cap = INT_MAX;
for(int v = dest; v != src; v = parent[v])
{
const int u = parent[v];
path_min_cap = std::min(path_min_cap, capacity[u][v] - flow[u][v]);
}
for(int v = dest; v != src; v = parent[v])
{
const int u = parent[v];
flow[u][v] += path_min_cap;
flow[v][u] -= path_min_cap;
}
max_flow += path_min_cap;
}
return max_flow;
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
for(int i = 0; i < m; ++i)
{
int a, b, w;
std::cin >> a >> b >> w;
adj[a].push_back({b, w});
}
const WeightedGraph g(n, std::move(adj));
const auto dists = g.distante_minime_dijkstra(1);
for(int node = 2; node <= n; ++node)
{
auto dist = dists[node];
if(dist == INT_MAX)
{
dist = 0;
}
std::cout << dist << ' ';
}
std::cout << '\n';
}
static const int redirect_io = []()
{
std::freopen("dijkstra.in", "r", stdin);
std::freopen("dijkstra.out", "w", stdout);
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
return 0;
}();
Nicula Ionut icnsr