#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define pb push_back
#include <vector>
#include <set>
#define LE 50666
#define pii pair<int,int>
#define x first
#define y second
#define mp make_pair

struct comp
{
    bool operator()(pii A,pii B)
    {
        return A.y<B.y;
    }
};

int n,m,i,j,yy,xx,cost;
vector<pair<int,int> > H[LE];
set<pair<int,int>,comp> Heap;
bool fr[LE];
int dp[LE],nodes;

int main()
{
    f>>n>>m;
    for(i=1; i<=m; ++i)
    {
        f>>xx>>yy>>cost;
        H[xx].pb(mp(yy,cost));
    }

    Heap.insert(mp(1,0));

    while (Heap.empty()==false)
    {
        pii next=*Heap.begin();
        Heap.erase(Heap.begin());

        if (fr[next.x]==true) continue;

        fr[next.x]=true;
        dp[next.x]=next.y;

        int N=H[next.x].size();

        for(i=0; i<N; ++i)
            if (fr[H[next.x][i].x]==false)
                Heap.insert(mp(H[next.x][i].x,next.y+H[next.x][i].y));
    }

    for(i=2; i<=n; ++i)
        g<<dp[i]<<" ";

    g<<'\n';

    f.close();
    g.close();
    return 0;
}