#include <bits/stdc++.h>

using namespace std;

const int inf=2e9;

struct node {
    int val, B, nod;
    node *vec, *tata, *dr;
    node(int x, int y) {
        val = x;
        nod = y;
        B = 0;
        vec = nullptr;
        tata = nullptr;
        dr = nullptr;
    }
};

map<int, node*> mp; ///for deletion

///merge two binomial trees and return the resulting tree
node* mergeTrees(node* t1, node*t2) {
    if (t1->val > t2->val) swap(t1, t2);
    t2->tata = t1;
    t2->dr = t1->vec;
    t1->vec = t2;
    t1->B++;
    return t1;
}

///merge two binomial heaps and return the resulting heap
vector<node*> mergeHeaps(vector<node*> &h1, vector<node*> &h2) {
    vector<node*> newH;
    int pos1 = 0, pos2 = 0;
    while (pos1 < h1.size() or pos2 < h2.size()) {
        if (pos1 == h1.size()) {
            newH.push_back(h2[pos2]);
            pos2++;
        }
        else if (pos2 == h2.size()) {
            newH.push_back(h1[pos1]);
            pos1++;
        }
        else if (h1[pos1]->val <= h2[pos2]->val) {
            newH.push_back(h1[pos1]);
            pos1++;
        }
        else {
            newH.push_back(h2[pos2]);
            pos2++;
        }
    }
    /// adjust the new heap so that trees are in increasing order of degree and have different degree.
    if (newH.size() <= 1) return newH;
    vector<node*> aux;
    aux.push_back(newH[0]);
    for (int i = 1; i < newH.size(); ++i)
        if (aux.back()->B < newH[i]->B) aux.push_back(newH[i]);
        else if (aux.back()->B == newH[i]->B) aux.back() = mergeTrees(aux.back(), newH[i]);
        else {
            swap(aux.back(),newH[i]);
            aux.push_back(newH[i]);
        }
    return aux;
}


///insert a binomial tree in a binomial heap
void insertTreeInHeap(vector<node*> &h, node* t) {
    vector<node*> aux;
    aux.push_back(t);
    h = mergeHeaps(h, aux);
}

///return the root with minimum value
node* getMin(vector<node*> &h) {
    if (h.size()==0) return nullptr;
    node* ans = h[0];
    for (int i = 1; i < h.size(); ++i)
        if (ans->val > h[i]->val) ans = h[i];
    return ans;
}

///remove the root of a binomial tree and return a binomial heap
vector<node*> removeRootFromTree(node* root) {
    vector<node*> h;
    node *curr = root->vec;
    delete root;
    node *aux;
    while (curr) {
        aux = curr;
        curr = curr->dr;
        aux->dr = nullptr;
        aux->tata = nullptr;
        h.push_back(aux);
    }
    return h;
}

///delete the minimum value from a heap
void deleteMin(vector<node*> &h) {
    node* minRoot = getMin(h);
    if (minRoot == nullptr) return;
    vector<node*> aux;
    for (int i = 0; i < h.size(); ++i)
        if (h[i] != minRoot) aux.push_back(h[i]);
    h = removeRootFromTree(minRoot);
    h = mergeHeaps(aux, h);
}

///delete a node from a heap
void removeNodeFromHeap(vector<node*> &h, node* nod) {
    if(nod == nullptr) return;
    while(nod->tata) {
        swap(nod->val, nod->tata->val);
        nod = nod->tata;
    }
    vector<node*> aux;
    for (int i = 0; i < h.size(); ++i)
        if (h[i] != nod) aux.push_back(h[i]);
    h = removeRootFromTree(nod);
    h = mergeHeaps(aux, h);
}

///insert a new value in a heap
void insertVal(vector<node*> &h, int nod, int val) {
    node* aux = new node(val, nod);
    //mp[val] = aux; ///for deletion
    insertTreeInHeap(h, aux);
}

///build a heap with elements from an array
/*vector<node*> buildHeap(vector<int> &v) {
    vector<node*> newheap;
    for(int x : v)
        insertVal(newheap, x);
    return newheap;
}*/

///print the minimum value from a heap
void printMinVal(vector<node*> &h) {
    node* ans = getMin(h);
    if (ans == nullptr) printf("Heap is empty\n");
    else printf("%d\n", ans->val);
}

struct edge
{
    int x,c;
    bool operator <(const edge &aux) const
    {
        return c>aux.c;
    }
};

vector<edge> v[50010];
int d[50010];

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m,x,y,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[x].push_back({y,c});
    }
    for(int i=1;i<=n;i++) d[i]=inf;
    d[1]=0;
    vector<node*> q;
    insertVal(q, 1, 0);
    while(!q.empty())
    {
        node* aux = getMin(q);
        int nod=aux->nod,c=aux->val;
        deleteMin(q);
        if(d[nod]<c) continue;
        for(int i=0;i<v[nod].size();i++)
        {
            int vec=v[nod][i].x,c1=v[nod][i].c;
            if(c+c1<d[vec])
            {
                d[vec]=c+c1;
                insertVal(q, vec, d[vec]);
            }
        }
    }
    for(int i=2;i<=n;i++)
        if(d[i]<inf) printf("%d ",d[i]);
        else printf("0 ");
    return 0;
}