#include<cstdio>
#include<vector>
#include<utility>
#include<set>

#define N_MAX 50010
#define pb push_back
#define mp make_pair
#define INF 600000
using namespace std;

multiset < pair<int,int> > H;
vector < pair<int,int> > G[N_MAX];

int D[N_MAX],N;
bool use[N_MAX];

inline void Write_Data()
{
    int i;
    for (i=2;i<=N;i++)
        if (D[i]!=INF) printf("%d ",D[i]);
            else printf("0 ");
    printf("\n");
    return;
}

inline void Dijkstra()
{
    int nod,val;
    pair <int,int> x;
    vector < pair<int,int> > :: iterator it;
    while (!H.empty())
    {
        x=*(H.begin());
        val=x.first;
        nod=x.second;
        H.erase(H.begin());
        use[nod]=true;
        for (it=G[nod].begin();it!=G[nod].end();++it)
        {
            x=*it;
            if (x.second + val < D[x.first])
                {
                    if (D[x.first]!=INF) H.erase(H.find(mp(D[x.first],x.first)));
                    D[x.first]=val+x.second;
                    H.insert(mp(D[x.first],x.first));
                }
        }
    }
}

inline void Load_Data()
{
    int M,i,j,x,y,c;
    scanf("%d%d",&N,&M);
    for (i=1;i<=M;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        G[x].pb(mp(y,c));
    }
    for (i=1;i<=N;i++)
    {
        D[i]=INF;
        use[i]=false;
    }
    D[1]=0;
    H.insert(mp(0,1));
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    Load_Data();
    Dijkstra();
    Write_Data();
    fclose(stdin);
    fclose(stdout);
    return 0;
}