#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define MOD 1000000007
typedef long long ll;
typedef long double ld;
const int INF=(int)(1e9);
const ll INF64=(ll)(1e18);
const ld EPS=1e-9;
const ld PI=3.1415926535897932384626433832795;
const int N=100005;
vector<list<pair<int,int> > >adjList(N+1); // Always give size of adjList
list<pair<int,int> >::iterator it;
int parent[N+1];
int level[N+1];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq; // priority queue //Contains vertex and its distance
// greater<pair<int,int> > is used to change std::priority queue to min heap
pair<int,int>p;
int d[N+1]; // distances from starting point
int n,m;
void dijkstra(int start){
for(int i=1;i<=n;++i)
d[i]=INF;
d[start]=0;
// Preparing my priority queue
for(int i=1;i<=n;++i){
pq.push(mp(d[i],i));
}
int u,v,w;
int count=n;
while(count--){
int u=pq.top().ss; // get value of element ,leave its weight
pq.pop();
it=adjList[u].begin();
while(it!=adjList[u].end()){
int v=it->ff;
int w=it->ss;
if(d[u]+w<d[v]){
d[v]=d[u]+w;
pq.push(mp(d[v],v));
}
++it;
}
}
}
int main(){
int v1,v2,w;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d %d %d",&v1,&v2,&w);
adjList[v1].pb(mp(v2,w));
}
dijkstra(1); // start vertex goes in dijkstra
for(int i=1;i<=n;++i)
printf("%d\n",d[i]);
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBmZiBmaXJzdAojZGVmaW5lIHNzIHNlY29uZAojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG1wIG1ha2VfcGFpcgoKI2RlZmluZSBNT0QgMTAwMDAwMDAwNwoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgbG9uZyBkb3VibGUgbGQ7Cgpjb25zdCBpbnQgSU5GPShpbnQpKDFlOSk7CmNvbnN0IGxsIElORjY0PShsbCkoMWUxOCk7CmNvbnN0IGxkIEVQUz0xZS05Owpjb25zdCBsZCBQST0zLjE0MTU5MjY1MzU4OTc5MzIzODQ2MjY0MzM4MzI3OTU7Cgpjb25zdCBpbnQgTj0xMDAwMDU7Cgp2ZWN0b3I8bGlzdDxwYWlyPGludCxpbnQ+ID4gPmFkakxpc3QoTisxKTsgICAgLy8gQWx3YXlzIGdpdmUgc2l6ZSBvZiBhZGpMaXN0Cmxpc3Q8cGFpcjxpbnQsaW50PiA+OjppdGVyYXRvciBpdDsKaW50IHBhcmVudFtOKzFdOwppbnQgbGV2ZWxbTisxXTsKcHJpb3JpdHlfcXVldWU8cGFpcjxpbnQsaW50Pix2ZWN0b3I8cGFpcjxpbnQsaW50PiA+LGdyZWF0ZXI8cGFpcjxpbnQsaW50PiA+ID5wcTsgLy8gcHJpb3JpdHkgcXVldWUgICAgLy9Db250YWlucyB2ZXJ0ZXggYW5kIGl0cyBkaXN0YW5jZQoKLy8gIGdyZWF0ZXI8cGFpcjxpbnQsaW50PiA+IGlzIHVzZWQgdG8gY2hhbmdlIHN0ZDo6cHJpb3JpdHkgcXVldWUgdG8gbWluIGhlYXAKCnBhaXI8aW50LGludD5wOyAgICAKCmludCBkW04rMV07ICAgIC8vICBkaXN0YW5jZXMgZnJvbSBzdGFydGluZyBwb2ludAoKaW50IG4sbTsKCnZvaWQgZGlqa3N0cmEoaW50IHN0YXJ0KXsKICAgIAogICAgZm9yKGludCBpPTE7aTw9bjsrK2kpCiAgICAgICAgZFtpXT1JTkY7CgogICAgZFtzdGFydF09MDsgCiAgICAvLyBQcmVwYXJpbmcgbXkgcHJpb3JpdHkgcXVldWUKICAgIGZvcihpbnQgaT0xO2k8PW47KytpKXsKIAogICAgICAgcHEucHVzaChtcChkW2ldLGkpKTsKICAgIH0KCiAgICBpbnQgdSx2LHc7ICAgIAogICAgaW50IGNvdW50PW47CiAgICAKICAgIHdoaWxlKGNvdW50LS0pewogICAgCiAgICAgICAgaW50IHU9cHEudG9wKCkuc3M7ICAgLy8gIGdldCB2YWx1ZSBvZiBlbGVtZW50ICxsZWF2ZSBpdHMgd2VpZ2h0IAogICAgICAgIHBxLnBvcCgpOwoKICAgICAgICBpdD1hZGpMaXN0W3VdLmJlZ2luKCk7CgogICAgICAgIHdoaWxlKGl0IT1hZGpMaXN0W3VdLmVuZCgpKXsKICAgICAgICAgCiAgICAgICAgICAgICBpbnQgdj1pdC0+ZmY7CiAgICAgICAgICAgICBpbnQgdz1pdC0+c3M7CiAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgaWYoZFt1XSt3PGRbdl0pewogICAgICAgICAgICAgCiAgICAgICAgICAgICAgICBkW3ZdPWRbdV0rdzsKICAgICAgICAgICAgICAgIHBxLnB1c2gobXAoZFt2XSx2KSk7CiAgICAgICAgICAgICAKICAgICAgICAgICAgIH0gCiAgICAgICAgICAgICArK2l0OwogICAgICAgICB9CgogICAgfQoKfQoKaW50IG1haW4oKXsKIAogICAgIGludCB2MSx2Mix3OwoKICAgICBzY2FuZigiJWQgJWQiLCZuLCZtKTsKCiAgICAgZm9yKGludCBpPTE7aTw9bTsrK2kpewoKICAgICAgICAgICBzY2FuZigiJWQgJWQgJWQiLCZ2MSwmdjIsJncpOyAgIAogICAgICAgICAgIGFkakxpc3RbdjFdLnBiKG1wKHYyLHcpKTsgICAgCiAgICAgfQoKICAgICBkaWprc3RyYSgxKTsgIC8vIHN0YXJ0IHZlcnRleCBnb2VzIGluIGRpamtzdHJhCgogICAgIGZvcihpbnQgaT0xO2k8PW47KytpKQogICAgICAgICBwcmludGYoIiVkXG4iLGRbaV0pOwoKICAgICByZXR1cm4gMDsKfQo=