// Sursa nu e a mea!
// Este a lui Barbu Ion
// Testez deoarece la mine imi dau toate testele "incorect", desi cand le testez la mine rezultatul este identic
#include <fstream>
#include<vector>
#include<set>
#define inf  0x3f3f3f3f
 
using namespace std;
vector< pair<int,int> >v[50001];
multiset < pair<int,int> > s;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,i,j,x,y,c,d[50001];
int main()
{
f>>n>>m;
for(i=1;i<=m;i++){
    f>>x>>y>>c;
    v[x].push_back(make_pair(y,c));
}
for(i=1;i<=n;i++)
    d[i]=inf;
d[0]=0;
s.insert(make_pair(0,1));
for(;s.size()>0;)
{
    multiset <pair <int, int> > :: iterator it = s.begin() ;
    int nod=(*it).second;
    int cost=(*it).first;
    s.erase(it);
    for(i=0;i<v[nod].size();i++){
      int vec=  v[nod][i].first;
      int ct=v[nod][i].second;
 
         if(d[vec]>cost+ct)
    {
        d[vec]=cost+ct;
 
        s.insert(make_pair(d[vec],vec));
    }
    }
}
for(i=2;i<=n;i++)
      if(d[i]==inf)
       g<<0<<" ";
else
    g<<d[i]<<" ";
    return 0;
}
/*#include <cstdio>
#include <utility>
#include <vector>
#include <queue>
using namespace std;

long N, M;
long viz[50001];
bool vz[50001];
vector<pair<long, long> > v[50001];
queue<long> q;
long a, b, l;

int main() {
    long i, j, crt;
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%ld %Ld", &N, &M);
    for(i = 1; i <= M; i++) {
        scanf("%ld %ld %ld", &a, &b, &l);
        v[a].push_back(make_pair(b, l));
        //v[b].push_back(make_pair(a, l));
    }
    vz[1] = true;
    viz[1] = 0;
    q.push(1);
    while(!q.empty()) {
        crt = q.front();
        for(i = 0; i < v[crt].size(); i++) {
            if(!vz[v[crt][i].first] || viz[v[crt][i].first] > v[crt][i].second + viz[crt]) {
                vz[v[crt][i].first] = true;
                viz[v[crt][i].first] = v[crt][i].second + viz[crt];
                q.push(v[crt][i].first);
            }
        }
        q.pop();
    }
    for(i = 2; i <= N; i++) {
        printf("%ld ", viz[i]);
    }
    //printf("\n");
    return 0;
}
*/