#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <fstream>
#define maxn 50010
#define infinit 0x3f3f3f

using namespace std;

struct nod {int inf,cost; nod*urm;} *g[maxn];

int n,m,dist[maxn];
int viz[maxn];

struct cmp
{
    bool operator()(const int &a, const int &b) const
    {
        return dist[a]>dist[b];
    }
};

priority_queue <int, vector<int>, cmp> Q;

void baga(int x, int y, int c)
{
    nod *q=new nod;
    q->inf=y;
    q->cost=c;
    q->urm=g[x];
    g[x]=q;
}

void dijkstra()
{
    for(int i=2;i<=n;i++)
        dist[i]=infinit;
    Q.push(1);
    int top, D, no, dis;
    while(!Q.empty())
    {
        top=Q.top();
        Q.pop();
        viz[top]=0;
        D=dist[top];
        for(nod *q=g[top];q;q=q->urm)
        {
            no=q->inf;
            dis=q->cost;
            if(D+dis<dist[no])
            {
                dist[no]=D+dis;
                if(!viz[no])
                {
                    viz[no]=1;
                    Q.push(no);
                }
            }
        }
    }
}

int main()
{
    ifstream f("dijkstra.in");
    f>>n>>m;
    int x,y,c;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        baga(x,y,c);
    }
    dijkstra();
    freopen("dijkstra.out","w",stdout);
    for(int i=2;i<=n;i++)
        printf("%d ",dist[i]);
    printf("\n");
    fclose(stdout);
    return 0;
}