#include <fstream>
#include <vector>
using namespace std;

const int N=100005,inf=1<<30;
struct nod{int x,c;};
int v[5*N],dist[N],n;
bool use[N];
vector<nod> a[N];

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

inline bool cmp(int a,int b)
{
    return dist[a]<dist[b];
}

inline void sch(int &a,int &b)
{
    int c=a;a=b;b=c;
}

void up(int x)
{
    if (x>1 && cmp(v[x],v[x>>1]))
    {
        sch(v[x],v[x>>1]);
        up(x>>1);
    }
}

void down(int x)
{
    int m=x,S=x<<1,D=S+1;
    if (S<=v[0] && cmp(v[S],v[m]))
        m=S;
    if (D<=v[0] && cmp(v[D],v[m]))
        m=D;
    if (m!=x)
    {
        sch(v[x],v[m]);
        down(m);
    }
}

void push(int x)
{
    v[++v[0]]=x;
    up(v[0]);
}

void pop(int &x)
{
    x=v[1];
    v[1]=v[v[0]--];
    down(1);
}

void dijkstra(int x)
{
    for (int i=1;i<=n;i++)
    {
        dist[i]=inf;
        use[i]=false;
    }
    dist[x]=0;
    push(x);
    while (v[0])
    {
        pop(x);
        if (use[x])
            continue;
        use[x]=true;
        for (vector<nod>::iterator i=a[x].begin();i!=a[x].end();i++)
        {
            int y=(*i).x,c=(*i).c;
            if (dist[x]+c < dist[y])
            {
                dist[y]=dist[x]+c;
                push(y);
            }
        }
    }
}

int main()
{
    int m,x,y,c;
    in>>n>>m;
    while (m--)
    {
        in>>x>>y>>c;
        a[x].push_back((nod){y,c});
    }
    dijkstra(1);
    for (int i=2;i<=n;i++)
        out<<(dist[i]!=inf ? dist[i] : 0)<<" ";
    out<<"\n";
    return 0;
}