#include<iostream>
#include<vector>
#include<string>
#include<cmath>
//#include "fibo_heaps.cpp"

using namespace std;

#define INF 1 << 30
#define NMAX 50001
#define min(a,b) ((a<b)?a:b)

struct node
{
    int key;
    int value;
    int degree;
    node* parent;
    node* child;
    node* last_child;
    node* left;
    node* right;
    bool marked;
};

class FiboHeap
{
    private:
        void CreateHeap();
        void ConsolidateHeap();
        void Concatenate(node* source, node* dest);
        void RecErase(node *root);

        void showInnerTree(node* root,int sp);

        node* lastof_roots;
    public:
        int totalNodes;
        node* minH;
        node* roots;

        FiboHeap();
        ~FiboHeap();
        void InsertNodeIntoHeap(node* toAdd);
        void InsertValueIntoHeap(int value);
        void InsertKeyValueIntoHeap(int value,int key);
        static FiboHeap HeapUnion(FiboHeap H1, FiboHeap H2);
        node ExtractMinHeap();
        int PeekMinimum();
        void insertRootList(node* rootlist,node* lastof_roots_toins);
        void DecrementKey(node* x, int newvalue);
        void Cut(node* x, node* x_parent);
        void CascadeCut(node* y);

        void showTree();
};

void FiboHeap::CreateHeap()
{
    totalNodes=0;
    minH=NULL;
    roots=NULL;
}

void FiboHeap::ConsolidateHeap()
{
    int logN=(int)((double)log(totalNodes)/log(2))+1;
    vector<node*> A(logN);
    for(int i=0;i<logN;i++)
        A[i]=NULL;
    for(node* it=roots;it;it=it->right)
    {
        node* x=it;
        int d=x->degree;
        while(A[d]!=NULL && A[d]!=x)
        {
            node* y=A[d];
            if(x->value>y->value)
            {
                node* aux=x;
                x=y;
                y=aux;
            }
            Concatenate(y,x);
            A[d]=NULL;
            d++;
        }
        A[d]=x;
        it=x;
    }
    minH=NULL;
    for(int i=0;i<logN;i++)
        if(A[i]!=NULL)
        {
            if(!minH || A[i]->value<minH->value)
                minH=A[i];
        }
}

void FiboHeap::Concatenate(node* source, node* dest)
{
    if(source->left)
        source->left->right=source->right;
    else roots=source->right;
    if(source->right)
        source->right->left=source->left;
    else lastof_roots=source->left;

    source->right=NULL;
    source->left=NULL;
    if(dest->child==NULL)
    {
        dest->child=source;
        dest->last_child=dest->child;
    }
    else
    {
        source->left=dest->last_child;
        source->left->right=source;
        dest->last_child=dest->last_child->right;
    }
    source->parent=dest;
    dest->degree++;
    dest->marked=false;
}

FiboHeap::FiboHeap()
{
    CreateHeap();
}

void FiboHeap::RecErase(node* root)
{
    if(root->child)
    for(node *it=root->child;it;)
    {
        node *p=it->right;
        RecErase(it);
        delete it;
        it=p;
    }
}

FiboHeap::~FiboHeap()
{
    for(node *it=roots;it;)
    {
        node *p=it->right;
        RecErase(it);
        delete it;
        it=p;
    }
}

void FiboHeap::InsertNodeIntoHeap(node* toAdd)
{
    toAdd->degree=0;
    toAdd->parent=NULL;
    toAdd->child=NULL;
    toAdd->last_child=NULL;
    toAdd->left=NULL;
    toAdd->right=NULL;
    toAdd->marked=false;
    if(roots==NULL)
    {
        roots=toAdd;
        lastof_roots=roots;
    }
    else{
        lastof_roots->right=toAdd;
        lastof_roots->right->left=lastof_roots;
        lastof_roots=lastof_roots->right;
    }
    if(!minH || toAdd->value<minH->value)
        minH=toAdd;
    totalNodes++;
}

void FiboHeap::InsertValueIntoHeap(int value)
{
    node* toAdd=new node;
    toAdd->key=0;
    toAdd->value=value;
    toAdd->degree=0;
    toAdd->parent=NULL;
    toAdd->child=NULL;
    toAdd->last_child=NULL;
    toAdd->left=NULL;
    toAdd->right=NULL;
    toAdd->marked=false;
    if(roots==NULL)
    {
        roots=toAdd;
        lastof_roots=roots;
    }
    else{
        lastof_roots->right=toAdd;
        lastof_roots->right->left=lastof_roots;
        lastof_roots=lastof_roots->right;
    }
    if(!minH || (toAdd->value<minH->value))
        minH=toAdd;
    totalNodes++;
}

void FiboHeap::InsertKeyValueIntoHeap(int value, int key)
{
    node* toAdd=new node;
    toAdd->key=key;
    toAdd->value=value;
    toAdd->degree=0;
    toAdd->parent=NULL;
    toAdd->child=NULL;
    toAdd->last_child=NULL;
    toAdd->left=NULL;
    toAdd->right=NULL;
    toAdd->marked=false;
    if(roots==NULL)
    {
        roots=toAdd;
        lastof_roots=roots;
    }
    else{
        lastof_roots->right=toAdd;
        lastof_roots->right->left=lastof_roots;
        lastof_roots=lastof_roots->right;
    }
    if(!minH || (toAdd->value<minH->value))
        minH=toAdd;
    totalNodes++;
}

int FiboHeap::PeekMinimum()
{
    if(minH)
        return minH->value;
    else
        return -((2<<31)-1);
}

void FiboHeap::insertRootList(node* rootlist,node* lastof_roots_toins)
{
    if(lastof_roots)
    {
        lastof_roots->right=rootlist;
        if(rootlist)
            lastof_roots->right->left=lastof_roots;
    }
    else roots=rootlist;
    lastof_roots=lastof_roots_toins;
}

FiboHeap FiboHeap::HeapUnion(FiboHeap H1, FiboHeap H2)
{
    FiboHeap H;
    H.minH=H1.minH;
    H.roots=H1.roots;
    H.lastof_roots=H1.lastof_roots;
    H.insertRootList(H2.roots,H2.lastof_roots);
    if(!H1.minH || (H2.minH && H2.minH->value<H1.minH->value))
        H.minH=H2.minH;
    H.totalNodes=H1.totalNodes+H2.totalNodes;
    return H;
}

node FiboHeap::ExtractMinHeap()
{
    node* z=minH;
    node p=*z;
    if(z)
    {
        for(node* it=z->child;it;it=it->right)
        {
            node* x=it;
            lastof_roots->right=x;
            x->left=lastof_roots;
            x->parent=NULL;
            lastof_roots=x;
        }

        if(z->left)
            z->left->right=z->right;
        else roots=z->right;
        if(z->right)
            z->right->left=z->left;
        else lastof_roots=z->left;

        minH=z->right;
        ConsolidateHeap();

        totalNodes--;
        delete z;
    }
    return p;
}

void FiboHeap::DecrementKey(node* x,int newvalue)
{
    if(newvalue>x->value)
        return;
    x->value=newvalue;
    node* y=x->parent;
    if(y && x->value<y->value)
    {
        Cut(x,y);
        CascadeCut(y);
    }
    if(x->value<minH->value)
        minH=x;
}

void FiboHeap::Cut(node* x,node* x_parent)
{
    node* y=x_parent;

    if(x->left)
        x->left->right=x->right;
    else  y->child=x->right;
    if(x->right)
        x->right->left=x->left;
    else y->last_child=x->left;

    x->parent=NULL;

    x->right=NULL;
    x->left=NULL;

    lastof_roots->right=x;
    lastof_roots->right->left=lastof_roots;
    lastof_roots=lastof_roots->right;

    x->marked=false;
    y->degree--;
}

void FiboHeap::CascadeCut(node* y)
{
    node* z=y->parent;
    if(z)
    {
        if(y->marked==false)
            y->marked=true;
        else
        {
            Cut(y,z);
            CascadeCut(z);
        }
    }
}

void FiboHeap::showInnerTree(node* root, int sp)
{
    if(root->child)
    {
        for(node* it=root->child;it;it=it->right)
        {
            cout.width(sp*4);
            cout<<it->value<<"\n";
            showInnerTree(it,sp+1);
        }
    }
}

void FiboHeap::showTree()
{
    for(node* it=roots;it;it=it->right)
    {
        cout<<it->value<<"\n";
        showInnerTree(it,1);
    }
}

int n,m,start,end;
vector<int> viz,par;

vector<pair<int,int> > G[NMAX];
vector<node> DR;

FiboHeap H;

void citire()
{
    cin>>n>>m;
    start=1;
    end=n;

    viz=vector<int>(n+1,0);
    par=vector<int>(n+1,0);
    DR=vector<node>(n+1);

    int x,y,c;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
        G[y].push_back(make_pair(x,c));
    }

    for(int i=1;i<=n;i++)
    {
        node l;
        l.key=i;
        l.value=INF;
        DR[i]=l;
        H.InsertNodeIntoHeap(&DR[i]);
    }
}

void rezolva()
{
    viz[start]=1;
    par[start]=0;
    vector<pair<int,int> >::iterator it;
    for(it=G[start].begin();it!=G[start].end();it++)
    {
        int nod=(*it).first;
        int cost=(*it).second;
        par[nod]=start;
        H.DecrementKey(&DR[nod],cost);
    }

    int ok=1,drmin,poz;
    while(ok)
    {
        drmin=INF;
        node k=H.ExtractMinHeap();
        drmin = k.value;
        poz = k.key;

        if(drmin==INF)
            ok=0;
        else
        {
            viz[poz]=1;
            for(it=G[poz].begin();it!=G[poz].end();it++)
            {
                int nod=(*it).first;
                int cost=(*it).second;
                if(!viz[nod])
                {
                    int aux=DR[poz].value+cost;
                    if(DR[nod].value>aux){
                        H.DecrementKey(&DR[nod],aux);
                        par[nod]=poz;
                    }
                }
            }
        }
    }
}

void afiseaza()
{
    for(int i=2;i<=n;i++)
        cout<<DR[i].value<<" ";
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    citire();
    rezolva();
    afiseaza();
    return 0;
}