#include<cstdio>
#include<vector>
#include<bitset>
#include<queue>

using namespace std;

typedef pair<int,int> PII;
const int INF = (1<<31)-1;
const int NMAX = 50000+2;

struct cmp
{
    bool operator()(const PII &A, const PII &B)
    {
        if(A.second==B.second) return A.first>B.first;
        return A.second>B.second;
    }
};

int N,M;
vector<PII> V[NMAX];
int Dist[NMAX];
bitset<NMAX> Viz;
priority_queue<PII,vector<PII>,cmp> PQ;

void Dijkstra()
{
    int i,x;
    vector<PII>::iterator y;

    for(i=1; i<=N; i++)
        Dist[i]=INF;

    Dist[1]=0;
    PQ.push(make_pair(1,0));

    while(!PQ.empty())
    {
        x=PQ.top().first;
        PQ.pop();
        Viz[x]=0;

        for(y=V[x].begin(); y!=V[x].end(); y++)
            if(Dist[y->first] > Dist[x] + y->second)
            {
                Dist[y->first]=Dist[x] + y->second;
                if(!Viz[y->first]) PQ.push(make_pair(y->first,Dist[y->first])),Viz[y->first]=1;
            }
    }
}

int main()
{
    int i,x,y,c;

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    scanf("%d%d",&N,&M);

    for(; M; --M)
    {
        scanf("%d%d%d",&x,&y,&c);
        V[x].push_back(make_pair(y,c));
    }

    Dijkstra();

    for(i=2; i<=N; i++)
        printf("%d ",Dist[i]);

    return 0;
}