#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define INF 1<<30


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

vector< pair<long long,long long> > a[50010];
long long h[50100], poz[50010], d[50010], n, m, k;

void siftUp(long long nod)
{
    long long p=poz[nod];
    while(p>1&&d[h[p]]<d[h[p/2]])
    {
        swap(poz[h[p]], poz[h[p/2]]);
        swap(h[p], h[p/2]);
        p/=2;
    }
}

void siftDown(long long nod)
{
    long long tata=poz[nod], fiu=tata*2;
    while(fiu<=k)
    {
        if(fiu<k&&d[h[fiu]]>d[h[fiu+1]]) fiu++;
        if(d[h[fiu]]<d[h[tata]])
        {
            swap(poz[h[tata]], poz[h[fiu]]);
            swap(h[tata], h[fiu]);
            tata=fiu;
            fiu=tata*2;
        }
        else break;
    }

}

void update(long long nod, long long val)
{
    long long p=poz[nod];
    while(p>1)
    {
        swap(poz[h[p]], poz[h[p/2]]);
        swap(h[p], h[p/2]);
        p/=2;
    }
    d[h[1]]=val;
    siftDown(h[1]);
}

void addHeap(long long nod, long long val)
{
    h[++k]=nod;
    d[h[k]]=val;
    poz[nod]=k;
    siftUp(nod);
}

void popHeap()
{
    swap(poz[h[1]], poz[h[k]]);
    swap(h[1], h[k]);
    k--;
    siftDown(h[1]);
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        long long x, y, c;
        fin>>x>>y>>c;
        a[x].push_back(make_pair(y, c));
    }
    addHeap(1, 0);
    while(k)
    {
        long long nod=h[1];
        popHeap();
        for(int i=0;i<a[nod].size();++i)
        {
            long long vec=a[nod][i].first;
            long long cost=a[nod][i].second;
            if(poz[vec]==0) addHeap(vec, d[nod]+cost);
            else if(d[nod]+cost<d[vec])
            {
                update(vec, d[nod]+cost);
            }
        }
    }
    for(int i=2;i<=n;++i) fout<<d[i]<<" ";
    return 0;
}