#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#define pii pair<int,int>
#define bufferSize 100000
#define Nmax 50005
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,mn[Nmax],a,b,c,p;
vector<pii> v[Nmax],H;
char buffer[bufferSize+2];

bool digit(int a){return a>='0' && a<='9';}

void read(int &x){
    x = 0;
    while (!digit(buffer[p])){
        p++;
        if (p>=bufferSize){
            p = 0;
            f.read(buffer,bufferSize);
        }
    }
    while (digit(buffer[p])){
        x = x*10+buffer[p]-'0';
        p++;
        if (p>=bufferSize){
            p = 0;
            f.read(buffer,bufferSize);
        }
    }
}

bool comp(pii a,pii b){return a.second<b.second;}

int main()
{
    f.read(buffer,bufferSize);
    read(n);read(m);

    for (int i=1;i<=m;i++){
        read(a);read(b);read(c);
        v[a].push_back({b,c});
    }

    H.push_back({1,0});
    memset(mn,0x3f,sizeof(mn));
    mn[1] = 0;
    while (!H.empty()){
        pii nod = H[0];
        pop_heap(H.begin(),H.end(),comp);
        H.pop_back();

        if (nod.second>mn[nod.first]) continue;

        for(auto it : v[nod.first]){
            if (it.second+nod.second<mn[it.first]){
                mn[it.first] = it.second+nod.second;
                H.push_back({it.first,mn[it.first]});
                push_heap(H.begin(),H.end(),comp);
            }
        }
    }

    for (int i=2;i<=n;i++){
        if (mn[i]>1e9) mn[i] = 0;
        g<<mn[i]<<' ';
    }

    return 0;
}