#include    <iostream>
#include    <fstream>
#include    <queue>
#include    <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int NMax = 50005;
const int oo = (1 << 30);
int N, M;
int drum[NMax];
bool ok[NMax];
vector < pair <int,int> > v[NMax];
struct prioritate
{
    bool operator()(int a,int b)
    {
        return drum[a]>drum[b];
    }
};
priority_queue<int, vector<int>,prioritate>q;

void read()
{
    f>>N>>M;
    for(int i=1;i<=M;++i)
    {
        int a, b, c;
        f>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
    }
}
void dj(int start)
{
    for(int i=1;i<=N;++i)
        drum[i]=oo;

    drum[start]=0;
    q.push(start);
    ok[start] = true;
    while(!q.empty())
    {
        int nc=q.top();
        q.pop();
        ok[nc]=false;
        for(int i=0;i<v[nc].size();++i)
        {
            int nod = v[nc][i].first;
            int lungime = v[nc][i].second;
            if(drum[nc]+lungime<drum[nod])
            {
                drum[nod]=drum[nc]+lungime;
                if(ok[nod]==false)
                {
                    q.push(nod);
                    ok[nod]=true;
                }
            }
        }
    }
}
void write()
{
    for(int i=2;i<=N;++i)
    {
        if(drum[i]!=oo)
            g<<drum[i]<<" ";
        else
            g<<"0 ";
    }
}
int main()
{
    read();
    dj(1);
    write();
}