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

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;
    int sum;
    bool operator < (const nod x) const
    {
        return ( d[x.val]+x.sum < d[(this->val)] + this->sum );
    }

};

void bfs()
{

    priority_queue < nod > Q;

    nod x;
    x.val=1;
    x.sum=0;

    Q.push(x);

    while(Q.empty()!=1)
    {
        f[x.val]=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;

                int sum=(*it).second+ d[x.val];
                if(d[copie.val]==0)
                {
                    d[copie.val]= sum;
                    Q.push(copie);
                }
                else if(d[copie.val]>sum)
                    d[copie.val]=sum;



            }
        }

        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;
}