#include <bits/stdc++.h>

std::vector<int> v[50000][2];
std::priority_queue< std::pair<int,int>, std::vector <  std::pair<int,int> >, std::greater<std::pair<int,int>> >pq;

int len[50000];

int best[50000];



int main()
{
    int n,m,a,b,cst,vl,nd,i;
    FILE*fi,*fo;
    fi=fopen("dijkstra.in","r");
    fo=fopen("dijkstra.out","w");
    fscanf(fi,"%d%d",&n,&m);
    for(i=0; i<m; i++)
    {
        fscanf(fi,"%d%d%d",&a,&b,&cst);
        a--;
        b--;
        v[a][0].push_back(b);
        v[a][1].push_back(cst);
        len[a]++;
    }
    pq.push({0,0});
    while(pq.empty()==0)
    {
        while(pq.empty()==0 && best[pq.top().second]!=0)
        {
            pq.pop();
        }
        if(pq.empty()==0)
        {
            vl=pq.top().first;
            nd=pq.top().second;
            best[nd]=vl;
            if(nd==0)
                best[nd]=1;
            for(i=0; i<len[nd]; i++)
            {
                if(best[v[nd][0][i]]==0)
                    pq.push({v[nd][1][i]+vl,v[nd][0][i]});
            }
        }
    }
    for(i=1; i<n; i++)
    {
        fprintf(fo,"%d ",best[i]);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}