#include <fstream>
#include <vector>
#include <queue>

#define pii pair<int, int>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector< pair<int,int> >M[50001];

int d[50001];
bool f[50001];

struct nod
{
    int val;

    bool operator < (const nod x) const
    {
        return ( d[x.val] < d[(this->val)]);
    }

};

void bfs()
{

    priority_queue < nod > Q;

    nod x;
    x.val=1;
    f[1]=1;

    Q.push(x);

    while(Q.empty()!=1)
    {
        x=Q.top();
        //fout<<x.val<<'\n';
        for(vector< pair<int,int> > :: iterator it=M[x.val].begin(); it!=M[x.val].end(); it++)
        {
            if(f[(*it).first]==0)
            {
                nod copie;

                copie.val=(*it).first;

                d[copie.val]= (*it).second+ d[x.val];

                Q.push(copie);

                f[(*it).first]=1;
            }
        }

        Q.pop();

    }
}

int main()
{
    int n,m,a,b,c;
    fin>>n>>m;
    for(int i=0; i<m; i++)
    {
        fin>>a>>b>>c;
        M[a].push_back({b,c});
    }

    bfs();

    for(int i=2; i<=n; i++)
    {
        fout<<d[i]<<" ";
    }
    return 0;
}