#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
const int NMAX = 1e5;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");
int main () {
// HAVEL HAKIMI -
//
//global
//
//// bool havelHakimi(int deg[NMAX+1], int m) {
//
// int sum=0;
// for (int i=0; i<m; i++) {
// sum+=deg[i];
// if (deg[i]>=m) return false;
// if (deg[i]<0) return false;
// }
// if ( sum%2 ==1 ) return false;
// sort(deg, deg+m, greater<int>());
// for (int i=0; i<m; i++) {
// int t=deg[i];
// if (t > m-i-1) return false;
// for (int j=i+1; j<i+t+1; j++) {
// deg[j]--;
// if (deg[j]<0) return false;
// }
// deg[i]=0;
// if (deg[i]>0 ) return false;
// sort(deg, deg+m, greater<int>());
// }
// return true;
// }
//
//main
//
// int n, m;
// in>>n;
// for (int i=0; i<n; i++) {
// in>>m;
// int deg[100001];
// for (int j=0; j<m; j++) {
// in>>deg[j];
// }
// int ok=havelHakimi(deg, m);
//
// if (ok==1) out<<"POSSIBLE"<<endl;
// else out<<"IMPOSSIBLE"<<endl;
// }
//BFS - distanta de la un nod S la restul nodurilor
// int n,m,a,b,s;
// in>>n>>m>>s;
// vector<vector<int> > adj(n+1);
//
// for (int i=0; i<m; i++) {
// in>>a>>b;
// adj[a].push_back(b);
// }
// vector<int> dist(n+1, -1);
// queue<int> q;
// dist[s]=0;
// q.push(s);
//
// while(!q.empty()) {
// int u=q.front();
// q.pop();
// for ( auto i : adj[u]) {
// if (dist[i]==-1) {
// dist[i]=dist[u]+1;
// q.push(i);
// }
// }
// }
//
// for ( int i=1; i<=n; i++ ) {
// out<<dist[i]<<" ";
// }
//DFS - cate componente conexe are un graf
// int n,m;
// in>>n>>m;
// vector<vector<int>> lista(1000000);
// for ( int i=1;i<=m;i++) {
// int x,y;
// in>>x>>y;
// lista[x].push_back(y);
// lista[y].push_back(x);
// }
//
// vector< int> vis(n+1, 0);
// vector<int> stack;
// int comp=0;
//
// for (int i=1;i<=n;i++) {
// if (!vis[i]) {
// comp++;
// stack.clear();
// stack.push_back(i);
// vis[i]=1;
// }
// else continue;
// while (!stack.empty()) {
// int u=stack.back();
// stack.pop_back();
// for ( auto v : lista[u]) {
// if ( !vis[v] ) {
// vis[v]=1;
// stack.push_back(v);
// }
// }
// }
// }
//
// out << comp << endl;
//BFS - berarie2 muchii inversate
// int n,m,p;
// in>>n>>m>>p;
// vector<vector<int> > adj (n+1);
// for ( int i = 1; i <= m; i++ ) {
// int x,y;
// in>>x>>y;
// adj[y].push_back(x);
// }
// queue<int> q;
// vector<int> vis (n+1,0);
//
// for (int i = 1; i <= p; i++ ) {
// int z;
// in>>z;
// if (!vis[z]) {
// vis[z] = 1;
// q.push(z);
// }
// }
//
// while ( !q.empty() ) {
// int x = q.front();
// q.pop();
// for ( auto v: adj[x] ) {
// if ( !vis[v] ) {
// vis[v] = 1;
// q.push(v);
// }
// }
// }
// vector<int> ans;
// for ( int i = 1; i <= n; i++ ) {
// if ( !vis[i] ) {
// ans.push_back(i);
// }
// }
// out<<ans.size()<<endl;
// for ( int i = 0; i < ans.size(); i++ ) {
// out<<ans[i]<<"\n";
// }
// KOSARAJU - determina ctc dintr-un graf
//
// asta e in global
//
// vector<vector<int>> g;
// vector<vector<int>> gT;
// vector<int> viz;
// stack<int> st;
//
// void dfs(int vf){
// viz[vf]=1;
// for (int x: g[vf]) {
// if (!viz[x])
// dfs(x);
//
// }
// st.push(vf);
// }
//
// void dfsT(int vf, vector<int> &v) {
// viz[vf]=1;
// v.push_back(vf);
// for ( int x : gT[vf]) {
// if (!viz[x])
// dfsT(x,v);
// }
// }
//
// asta e in main
//
// int n,m;
// in>>n>>m;
// g.resize(n+1);
// gT.resize(n+1);
// viz.assign(n+1, 0);
// for( int i=1;i<=m;i++) {
// int x,y;
// in>>x>>y;
// g[x].push_back(y);
// gT[y].push_back(x);
// }
//
// for ( int i=1;i<=n;i++) {
// if (!viz[i])
// dfs(i);
// }
// viz.assign(n+1,0);
// vector<vector<int>> comp;
//
// while (!st.empty()) {
// int vf = st.top();
// st.pop();
// if ( !viz[vf]) {
// vector<int> vv;
// dfsT(vf,vv);
// comp.push_back(vv);
// }
// }
//
// out<<comp.size()<<endl;
// for (vector<int> v : comp) {
// for (int x: v) {
// out<< x<< " ";
// }
// out<< endl;
// }
//SORTARE TOPOLOGICA
// global
// vector<vector<int>> adj;
// vector<int> viz, ord;
//
// void dfs(int vf) {
// viz[vf]=1;
// for ( auto x : adj[vf]) {
// if (!viz[x])
// dfs(x);
// }
// ord.push_back(vf);
// }
//
// main
// int n,m;
// in>>n>>m;
// viz.resize(n+1);
// adj.resize(n+1);
// ord.clear();
// for (int i=1;i<=m;i++) {
// int x,y;
// in>>x>>y;
// adj[x].push_back(y);
// }
// for ( int i =1; i<=n; i++) {
// if (!viz[i])
// dfs(i);
// }
//
// reverse(ord.begin(), ord.end());
//
// for ( int i : ord) out<< i<< " ";
//bipartit -colorare bfs mod
// int n,m;
// in>>n>>m;
// vector<vector<int> > adj(n+1);
// vector<int> color( n+1, 0);
// queue<int> q;
//
// for ( int i=1;i<=m;i++) {
// int x,y;
// in>>x>>y;
// adj[x].push_back(y);
// adj[y].push_back(x);
// }
//
// for (int i=1;i<=n;i++) {
// if (color[i]==0 ) {
// color[i]=1;
// q.push(i);
//
// while (!q.empty()) {
// int u=q.front();
// q.pop();
// for ( int x : adj[u]) {
// if ( color[x] == 0) {
// color[x]=3-color[u];
// q.push(x);
// }
// else if (color[x]==color[u]) {
// out<<"IMPOSSIBLE\n";
// return 0;
// }
// }
// }
// }
// }
// for ( int i =1; i<=n;i++)
// out<< color[i]<< " ";
// Tarjan - puncte de articulatie problema Vice City
//
//global
//
// vector<int> lista[NMAX+1];
// vector<bool> rez;
// int tin[NMAX+1], low[NMAX+1], timer;
//
// void dfs(int u, int parent) {
// int children=0;
// tin[u]= low[u]= ++timer;
// for ( int v: lista[u]) {
// if (v ==parent) continue;
// if (tin[v]== 0) {
// children++;
// dfs(v, u);
// low[u]=min(low[u],low[v]);
// if ( parent != -1 && low[v]>=tin[u])
// rez[u]= true;;
// }
// else{
// low[u]=min(low[u],tin[v]);
// }
// }
// if ( parent == -1 && children >=2 )
// rez[u]=true;
// }
//
//main
// int n,m;
// cin>>n>>m;
// while ( n!=0 && m!=0 ) {
//
// for( int i =0 ; i<= n; i++) lista[i].clear();
// timer=0;
// for( int i =0 ; i<= n; i++) tin[i]=low[i]=0;
// rez.assign(n+1, false);
//
// for ( int i=1;i<=m;i++) {
// int a,b;
// cin>>a>>b;
// lista[a].push_back(b);
// lista[b].push_back(a);
// }
//
// for ( int i =1; i<=n;i++) {
// if ( tin[i]==0)
// dfs(i,-1);
// }
// int ans=0;
// for (int i=1;i<=n;i++) {
// if (rez[i]) ans++;
// }
// cout<< ans<< '\n';
// cin>>n>>m;
// }
//
//KRUSKAL
//
//global
// struct Edge {
// int u,v,w;
// bool operator<( const Edge &m) const{
// return w<m.w;
// }
// };
//
// vector<Edge> apm,edg;
//
// int find(int x, vector<int> &v) {
// if (v[x]==0)
// return x;
// return find( v[x], v) ;
// }
//
// void unire ( int x, int y, vector< int> &tata , vector<int> &rang) {
// int rx= find( x, tata);
// int ry= find(y,tata);
//
// if ( rang[rx] < rang [ry]) swap (rx, ry);
// tata[ry]=rx;
// if ( rang[rx] == rang[ry]) rang[rx]++ ;
// }
//
//main
// int n,m,cost=0;
// in>>n>>m;
// for ( int i=1; i<=m;i++) {
// Edge e;
// in>>e.u>>e.v>> e.w;
// edg.push_back(e);
// }
//
// sort(edg.begin(), edg.end());
//
// vector<int> tata(n+1,0), rang(n+1,0);
// for ( auto &e: edg) {
// if ( apm.size() == n-1 )
// break;
// if ( find(e.u, tata)!= find( e.v,tata)) {
// cost+=e.w;
// apm.push_back(e);
// unire(e.u,e.v,tata, rang);
// }
// }
//
// out<< cost<< '\n';
// out<<apm.size()<<'\n';
//
// for ( auto &e: apm) {
// out<<e.u<<" "<<e.v<<'\n';
// }
//DIJKSTRA
int n,m;
in>>n>>m;
vector<vector< pair<int,int> >> adj(n+1);
for ( int i =1;i<=m;i++) {
int a,b,c;
in>>a>>b>>c;
adj[a].push_back({b,c});
}
const long long INF =1e18;
vector<long long> dist(n+1, INF);
dist[1]=0;
priority_queue< pair< long long, int>, vector<pair<long long,int>>, greater< pair< long long , int>>> pq;
pq.push({0,1});
while (!pq.empty()) {
auto [d,u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
for ( auto [v,w] : adj[u]) {
if (dist[v] > dist[u] +w) {
dist[v]= dist[u]+w;
pq.push({ dist[v], v});
}
}
}
for (int i=2;i<=n;i++) {
if ( dist[i] == INF ) out<< 0<<" ";
else out<<dist[i]<< " ";
}
return 0;
}
Moga Edi edimoga