#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
int n,m,comp[50005];
vector<int> mat[50005],d[50005];
int t[50005],p[50005];
class heap
{
public:
    int z[50005];
    int k;
    void insert(int a)
    {
        z[++k]=a;
		p[a]=k;
        int aux,q=k;
        while(t[z[q/2]]>t[z[q]]&&q/2>=1)
        {
            aux=z[q/2];
            z[q/2]=z[q];
            z[q]=aux;
            p[z[q]]=q/2;
            p[z[q/2]]=q;
            q=q/2;
        }
    }
    void remove(int i)
    {
        z[i]=z[k--];
        int q=k,aux;
        while(1)
        {
            q=i;
            if(t[z[i]]>t[z[i*2]]&&i*2<=k)
                q=i*2;
            if(t[z[q]]>t[z[i*2+1]]&&i*2+1<=k)
                q++;
            aux=z[q],z[q]=z[i],z[i]=aux;
            p[z[q]]=i; p[z[i]]=q;
            if(q==i) break;
            i=q;
        }
    }
    void up(int i)
    {
        int aux;
        while(t[z[i/2]]>t[z[i]]&&i/2>=1)
        {
            aux=z[i/2];
            z[i/2]=z[i];
            z[i]=aux;
            p[z[i/2]]=i;
            p[z[i]]=i/2;
            i=i/2;
        }
    }
};heap h;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int i,n1,n2,c,j,l;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        t[i]=2000000000;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&n1,&n2,&c);
        mat[n1].push_back(n2);
		mat[n2].push_back(n1);
		comp[n2]++;
        comp[n1]++;
        d[n1].push_back(c);
		d[n2].push_back(c);
    }
    t[1]=0;
    p[1]=1;
    h.k=0;
    h.insert(1);
    while(h.k>0)
    {
        i=h.z[1];
		h.remove(1);
        for(l=0;l<comp[i];l++)
        {
			j=mat[i][l];
            if(p[i]!=-1&&t[j]>t[i]+d[i][l])
			{
				if(t[j]==2000000000)
                {
                    t[j]=t[i]+d[i][l];
                    h.insert(j);
                }
                else
                {
                    t[j]=t[i]+d[i][l];
                    h.up(p[j]);
                }
			}
        }
        p[i]=-1;
    }
	for(i=2;i<=n;i++)
		printf("%d ",t[i]);

    return 0;
}